An independent transversal of a graph $G$ with a vertex partition $mathcal P$ is an independent set of $G$ intersecting each block of $mathcal P$ in a single vertex. Wanless and Wood proved that if each block of $mathcal P$ has size at least $t$ and the average degree of vertices in each block is at most $t/4$, then an independent transversal of $mathcal P$ exists. We present a construction showing that this result is optimal: for any $varepsilon > 0$ and sufficiently large $t$, there is a family of forests with vertex partitions whose block size is at least $t$, average degree of vertices in each block is at most $(frac14+varepsilon)t$, and there is no independent transversal. This unexpectedly shows that methods related to entropy compression such as the Rosenfeld-Wanles-Wood scheme or the Local Cut Lemma are tight for this problem. Further constructions are given for variants of the problem, including the hypergraph version.
تحميل البحث