2-colorings in k-regular k-uniform 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. The Lovász Local Lemma, devised by Erdös and Lovász in 1975 to tackle the problem of hypergraph 2-colorings, implies that every hypergraph H∈Hk is 2-colorable, provided k ≥ 9. Alon and Bregman [N.Alon, Z.Bregman, Every 8-uniform 8-regular hypergraph is 2-colorable, Graphs Combin. 4 (1988) 303-306] proved the slightly stronger result that every hypergraph H∈Hk is 2-colorable, provided k ≥ 8. It is implicitly known in the literature that the Alon-Bregman result is true for all k ≥ 4, as remarked by Vishwanathan [S.Vishwanathan, On 2-coloring certain k-uniform hypergraphs, J. Combin. Theory Ser. A 101 (2003) 168-172] even though we have not seen it explicitly proved. For completeness, we provide a short proof of this result. As remarked by Alon and Bregman the result is not true when k = 3, as may be seen by considering the Fano plane.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) {set minus} X such that every edge in H receives at least one vertex of each color. Equivalently, X is a free set in H if it is the complement of two disjoint transversals inH. For every k ≥ 13, we prove that every hypergraph H∈Hk of order n has a free set of size at least n / 5. For any ε where 0 < ε < 1 and for sufficiently large k, we prove that every hypergraph H∈Hk of order n has a free set of size at least _{c k}n, where _{c k} = 1 - 6 (1 + ε) ln (k) / k, and so _{c k} → 1 as k → ∞. As an application, we show that the total restrained domination number of a graph on n vertices with sufficiently large minimum degreek is at most12(1-ck)n, which significantly improves the best known bound of 12n+1.