Graphs of low average degree without independent transversals

Abstract

An independent transversal of a graph (Formula presented.) with a vertex partition (Formula presented.) is an independent set of (Formula presented.) intersecting each block of (Formula presented.) in a single vertex. Wanless and Wood proved that if each block of (Formula presented.) has size at least (Formula presented.) and the average degree of vertices in each block is at most (Formula presented.), then an independent transversal of (Formula presented.) exists. We present a construction showing that this result is optimal: for any (Formula presented.) and sufficiently large (Formula presented.), there is a forest with a vertex partition into parts of size at least (Formula presented.) such that the average degree of vertices in each block is at most (Formula presented.), 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.