The Lefthanded Local Lemma characterizes chordal dependency graphs

2012/04/26 by Wesley Pegden, Pegden, Wesley
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1204.5922

12 pages, 1 figure

arxiv created 2012/04/26 · arxiv updated 2012/04/27

Abstract

Shearer gave a general theorem characterizing the family \LLL of dependency graphs labeled with probabilities p_v which have the property that for any family of events with a dependency graph from \LLL (whose vertex-labels are upper bounds on the probabilities of the events), there is a positive probability that none of the events from the family occur. We show that, unlike the standard Lovász Local Lemma---which is less powerful than Shearer's condition on every nonempty graph---a recently proved `Lefthanded' version of the Local Lemma is equivalent to Shearer's condition for all chordal graphs. This also leads to a simple and efficient algorithm to check whether a given labeled chordal graph is in \LLL.

Related

• Directed Lovász Local Lemma and Shearer's Lemma
• Variable Version Lovász Local Lemma: Beyond Shearer's Bound
• The Lovász Local Lemma is Not About Probability
• Moser-Tardos Algorithm: Beyond Shearer's Bound
• Short proofs for generalizations of the Lovász Local Lemma: Shearer's condition and cluster expansion