1991/12/01 by József Beck · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems #Lemma (botany) #Hypergraph #Exponent #Mathematics #Sieve (category theory) #Constant (computer programming) #Monochromatic color #Discrete mathematics #Polynomial #Combinatorics #Time complexity #Computer science #Mathematical analysis #Physics
paper · doi:10.1002/rsa.3240020402
openalex publication_date 1991/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22
Abstract 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.