In 1994, ErdH{o}s, Gy{a}rf{a}s and {L}uczak posed the following problem: given disjoint vertex sets $V_1,dots,V_n$ of size~$k$, with exactly one edge between any pair $V_i,V_j$, how large can $n$ be such that there will always be an independent transversal? They showed that the maximal $n$ is at most $(1+o(1))k^2$, by providing an explicit construction with these parameters and no independent transversal. They also proved a lower bound which is smaller by a $2e$-factor. In this paper, we solve this problem by showing that their upper bound construction is best possible: if $nle (1-o(1))k^2$, there will always be an independent transversal. In fact, this result is a very special case of a much more general theorem which concerns independent transversals in arbitrary partite graphs that are `locally sparse, meaning that the maximum degree between each pair of parts is relatively small. In this setting, Loh and Sudakov provided a global emph{maximum} degree condition for the existence of an independent transversal. We show that this can be relaxed to an emph{average} degree condition. We can also use our new theorem to establish tight bounds for a more general version of the ErdH{o}s--Gy{a}rf{a}s--{L}uczak problem and solve a conjecture of Yuster from 1997. This exploits a connection to the Turan numbers of complete bipartite graphs, which might be of independent interest. Finally, we discuss some partial results on the hypergraph variant of the problem, and formulate a conjecture in this case.
Download