Directed Lovász local lemma and Shearer's lemma

DOI10.1007/S10472-019-09671-5zbMATH Open1477.68534arXiv1611.00502OpenAlexW2989678884WikidataQ124813178 ScholiaQ124813178MaRDI QIDQ2294597FDOQ2294597

Authors: L. M. Kirousis, John Livieratos, Kostas I. Psaromiligkos 

Publication date: 11 February 2020

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1611.00502

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

zbMATH Keywords

Shearer's lemmalopsided dependencyLovász local lemma

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A constructive proof of the general Lovász local lemma
• A constructive proof of the Lovász local lemma
• Lopsided Lovász Local lemma and Latin transversals
• On a problem of Spencer
• On the algorithmic Lovász local lemma and acyclic edge coloring
• Moser and tardos meet Lovász
• Upper bounds on the size of covering arrays
• A multivariate Lagrange inversion formula for asymptotic calculations
• The Lovász Local Lemma – A Survey
• Random walks that find perfect objects and the Lovász local lemma
• A constructive algorithm for the Lovász local lemma on permutations
• Lopsidependency in the Moser-Tardos framework: beyond the lopsided Lovász local lemma

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)