On 2-Colorings of Hypergraphs

In this article, we continue the study of 2-colorings in hypergraphs. A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. Let Hk denote the class of all k-uniform k-regular hypergraphs. It is known (see Alon and Bregman [Graphs Combin. 4 (1988) 303-306] and Thomassen [J. Amer. Math. Soc. 5 (1992), 217-229] that every hypergraph H≥Hk is 2-colorable, provided k≥4. As remarked by Alon and Bregman the result is not true when k=3, as may be seen by considering the Fano plane. Indeed there are several constructions for building infinite families of hypergraphs in H3 that are not 2-colorable. Our main result in this paper is a strengthening of the above results. For this purpose, we define a set X of vertices in a hypergraph H to be a free set in H if we can 2-color V(H)?X such that every edge in H receives at least one vertex of each color. We conjecture that for k≥4, every hypergraph H≥Hk has a free set of size k-3 in H. We show that the bound k-3 cannot be improved for any k≥4 and we prove our conjecture when k≥{5,6,7,8}. Our proofs use results from areas such as transversal in hypergraphs, cycles in digraphs, and probabilistic arguments.