Algorithmic version of general Lovász local lemma is true

Combinatorics, Mathematics of Computation 1 Minute

You need to know: Probability, probability space, event, random variable, mutually independent random variables.

Background: Let {\cal P} be a finite collection of mutually independent random variables in a fixed probability space \Omega. Let S be a finite family of events in \Omega determined by {\cal P}. For A\in S, let v(A) be the (unique) minimal subset of {\cal P} that determines A. For A\in S, let \Gamma_S(A) be the set of B\in S such that A\neq B but v(A)\cap v(B) \neq \emptyset. We say that an evaluation of the variables in {\cal P} violates A\in S if it makes A happen.

The Theorem: On 3rd March 2009, Robin Moser and Gábor Tardos submitted to arxiv a paper in which they proved that if there exists an assignment of reals x:S \to (0,1) such that \forall A\in S: \text{Prob}[A]\leq x(A) \prod\limits_{B\in \Gamma_S(A)} (1-x(B)), then there exists an assignment of values to the variables in {\cal P} not violating any of the events in S. Moreover, this assignment can be found by a randomised algorithm with the expected number of resampling steps at most \sum\limits_{A\in S}\frac{x(A)}{1-x(A)}.

Short context: The Theorem without “moreover” part is (a slightly modified version of) famous Lovász local lemma, discovered by Erdős and Lovász in 1975, which allows one to show the existence of certain objects occurring with exponentially small probability. The “moreover” part of the Theorem can be used to actually construct such objects. Previously, algorithmic versions where developed for some applications of the Lovász local lemma, but not for the lemma in general.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment