Hypergraph colouring and the Lovász Local Lemma

✍ Scribed by Colin McDiarmid

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 263 KB
• Volume: 167-168
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(96)00249-x

✦ Synopsis

The Lov~sz Local Lemma yields sufficient conditions for a hypergraph to be 2-colourable, that is, to have a colouring of the points blue or red so that no edge is monochromatic. The method yields a general theorem, which shows for example that, 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-colourable.

Here we see that this approach can go a little further: we use the 'lopsided' version of the Local Lemma to give an improved version of the theorem on hypergraph 2-colouring, from which it follows for example that the numbers 9,11 above may be replaced by 8,12.