The Lefthanded Local Lemma characterizes chordal dependency graphs

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$.

12 pages, 1 figure