A GENERAL FRAMEWORK FOR HYPERGRAPH COLORING

The Lovasz Local Lemma is a powerful probabilistic technique for proving the existence of combinatorial objects. It is especially useful for coloring graphs and hypergraphs with bounded maximum degree. This paper presents a general theorem for coloring hypergraphs that in many instances matches or slightly improves upon the bounds obtained using the Lovasz Local Lemma. Moreover, the theorem directly shows that there are exponentially many colorings. The elementary and self-contained proof is inspired by a recent result for nonrepetitive colorings by Rosenfeld [Electron. J. Combin., 27 (2020), P3.43]. We apply our general theorem in the settings of proper hypergraph coloring, proper graph coloring, independent transversals, star coloring, nonrepetitive coloring, frugal coloring, Ramsey number lower bounds, and k-SAT.

Automated summary

The Lovasz Local Lemma is a powerful probabilistic technique for proving the existence of combinatorial objects. This paper presents a general theorem for coloring hypergraphs that matches or slightly improves upon the bounds obtained using the Lovasz Local Lemma. The theorem also shows that there are exponentially many colorings. The proof is elementary and self-contained, inspired by recent results for nonrepetitive colorings. The authors apply the general theorem in various settings.