Graphs of low average degree without independent transversals

An independent transversal of a graphG $G$ with a vertex partitionP ${\mathscr{P}}$ is an independent set ofG $G$ intersecting each block ofP ${\mathscr{P}}$ in a single vertex. Wanless and Wood proved that if each block ofP ${\mathscr{P}}$ has size at leastt $t$ and the average degree of vertices in each block is at mostt ∕ 4 $t\unicode{x02215}4$ , then an independent transversal ofP ${\mathscr{P}}$ exists. We present a construction showing that this result is optimal: for anyε > 0 $\varepsilon \gt 0$ and sufficiently larget $t$ , there is a forest with a vertex partition into parts of size at leastt $t$ such that the average degree of vertices in each block is at most( 1 4 + ε ) t $(\frac{1}{4}+\varepsilon )t$ , and there is no independent transversal. This unexpectedly shows that methods related to entropy compression such as the Rosenfeld–Wanless–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.