Coloring and the Lovász Local Lemma

✍ Scribed by Xing Chen; Zhihua Du; Jixiang Meng

• Publisher: Elsevier Science
• Year: 2010
• Tongue: English
• Weight: 304 KB
• Volume: 23
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/j.aml.2009.02.008

✦ Synopsis

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.