Directed Lovász local lemma and Shearer's lemma
From MaRDI portal
Publication:2294597
Abstract: Moser and Tardos (2010) gave an algorithmic proof of the lopsided Lov'asz local lemma (LLL) in the variable framework, where each of the undesirable events is assumed to depend on a subset of a collection of independent random variables. For the proof, they define a notion of a lopsided dependency between the events suitable for this framework. In this work, we strengthen this notion, defining a novel directed notion of dependency and prove LLL for the corresponding graph. We show that this graph can be strictly sparser (thus the sufficient condition for LLL weaker) compared with graphs that correspond to other extant lopsided versions of dependency. Thus, in a sense, we address the problem "find other simple local conditions for the constraints (in the variable framework) that advantageously translate to some abstract lopsided condition" posed by Szegedy (2013). We also give an example where our notion of dependency graph gives better results than the classical Shearer lemma. Finally, we prove Shearer's lemma for the dependency graph we define. For the proofs, we perform a direct probabilistic analysis that yields an exponentially small upper bound for the probability of the algorithm that searches for the desired assignment to the variables not to return a correct answer within steps. In contrast, the method of proof that became known as the entropic method, gives an estimate of only the expectation of the number of steps until the algorithm returns a correct answer, unless the probabilities are tinkered with.
Recommendations
- Moser and tardos meet Lovász
- Lopsidependency in the Moser-Tardos framework: beyond the lopsided Lovász local lemma
- Lopsidependency in the Moser-Tardos framework: beyond the lopsided Lovász local lemma
- New constructive aspects of the Lovász local lemma
- Comparison of two convergence criteria for the variable-assignment lopsided Lovász local lemma
Cites work
- scientific article; zbMATH DE number 47926 (Why is no real title available?)
- scientific article; zbMATH DE number 3492718 (Why is no real title available?)
- A constructive algorithm for the Lovász local lemma on permutations
- A constructive proof of the Lovász local lemma
- A constructive proof of the general Lovász local lemma
- A multivariate Lagrange inversion formula for asymptotic calculations
- Lopsided Lovász Local lemma and Latin transversals
- Lopsidependency in the Moser-Tardos framework: beyond the lopsided Lovász local lemma
- Moser and tardos meet Lovász
- On a problem of Spencer
- On the algorithmic Lovász local lemma and acyclic edge coloring
- Random walks that find perfect objects and the Lovász local lemma
- The Lovász Local Lemma – A Survey
- Upper bounds on the size of covering arrays
Cited in
(10)- Correction to: ``Directed Lovász local lemma and Shearer's lemma
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Random walks that find perfect objects and the Lovász local lemma
- An algorithmic construction of union-intersection-bounded families
- Alternative proofs of the asymmetric Lovász local lemma and Shearer's lemma
- Quest for negative dependency graphs
- An extension of the Moser-Tardos algorithmic local lemma
- The lefthanded local lemma characterizes chordal dependency graphs
- The local cut lemma
- Comparison of two convergence criteria for the variable-assignment lopsided Lovász local lemma
This page was built for publication: Directed Lovász local lemma and Shearer's lemma
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294597)
