Premium
An algorithmic approach to the Lovász local lemma. I
Author(s) -
Beck József
Publication year - 1991
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240020402
Subject(s) - lemma (botany) , hypergraph , exponent , mathematics , sieve (category theory) , constant (computer programming) , monochromatic color , discrete mathematics , polynomial , combinatorics , time complexity , computer science , mathematical analysis , physics , ecology , linguistics , philosophy , poaceae , biology , programming language , optics
The Lovász Local Lemma is a remarkable sieve method to prove the existence of certain structures without supplying any efficient way of finding these structures. In this article we convert some of the applications of the Local Lemma into polynomial time sequential algorithms (at the cost of a weaker constant factor in the “exponent”). Our main example is the following: assume that in an n‐uniform hypergraph every hyperedge intersects at most 2 n/48 other hyperedges, then there is a polynomial time algorithm that finds a two‐coloring of the points such that no hyperedge is monochromatic.