22-colorings in kk-regular kk-uniform hypergraphs

A hypergraph is 22-colorable if there is a 22-coloring of the vertices with no monochromatic hyperedge. Let HkHk denote the class of all kk-uniform kk-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∈HkH∈Hk is 22-colorable, provided k≥9k≥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∈HkH∈Hk is 22-colorable, provided k≥8k≥8. It is implicitly known in the literature that the Alon–Bregman result is true for all k≥4k≥4, as remarked by Vishwanathan [S. Vishwanathan, On 2-coloring certain kk-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=3k=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 XX of vertices in a hypergraph HH to be a free set in HH if we can 22-color V(H)∖XV(H)∖X such that every edge in HH receives at least one vertex of each color. Equivalently, XX is a free set in HH if it is the complement of two disjoint transversals in HH. For every k≥13k≥13, we prove that every hypergraph H∈HkH∈Hk of order nn has a free set of size at least n/5n/5. For any ϵϵ where 0<ϵ<10<ϵ<1 and for sufficiently large kk, we prove that every hypergraph H∈HkH∈Hk of order nn has a free set of size at least cknckn, where ck=1−6(1+ϵ)ln(k)/kck=1−6(1+ϵ)ln(k)/k, and so ck→1ck→1 as k→∞k→∞. As an application, we show that the total restrained domination number of a graph on nn vertices with sufficiently large minimum degree kk is at most 12(1−ck)n, which significantly improves the best known bound of 12n+1.