Coloring and the Lovلsz Local Lemma

The Lovász Local Lemma yields sufficient conditions for a hypergraph to be 2-colorable, that is, to have a coloring of the points blue or red such that no edge is monochromatic. The method yields a general theorem, which shows for example, if H is a hypergraph in which each edge contains at least 9 points and each point is contained in at most 11 edges, then H is 2-colorable. In this paper, we use the ‘lopsided’ version of the Local Lemma to give some sufficient conditions on t -coloring to hypergraphs and 2-coloring to hypergraphs such that each edge contains at least 2 points of each color.