Lovász local lemma

LLL

A central technique in the probabilistic method. It is used to prove the existence of a "good" object even when the random object is almost certainly "bad" . It is applicable in situations in which the bad events are mostly independent. It sieves the bad events to find the rare good one.

Let $B_\alpha$, $\alpha \in I$, be a finite family of "bad" events. A graph $G$ on $I$ as vertex set is called a dependency graph for the events if each $B_\alpha$ is mutually independent of those $B_\beta$ with $\alpha, \beta$ not adjacent (cf. also Independence).

Symmetric case of the Lovász local lemma.

Let $B_\alpha$, $G$ be as above. Suppose all $\mathbf{P}[B_\alpha] \le p$. Suppose all $\alpha \in I$ are adjacent to at most $d$ other $\beta \in I$. Suppose $4dp < 1$. Then $\wedge_I \bar B_\alpha \neq \emptyset$.

Here, the number of events, $|I|$, may be arbitrarily large, giving the Lovász local lemma much of its strength. In most applications the underlying probability space is generated by mutually independent choices, each event $B_\alpha$ depends on a set $X_\alpha$ of choices, and $\alpha, \beta$ are adjacent when $X_\alpha,\,X_\beta$ overlap.

Example.

Let $A_\alpha$, $\alpha \in I$, be sets of size ten in some universe $\Omega$, where every $\omega \in \Omega$ lies in at most ten such sets. Then there is a red-blue colouring of $\Omega$ so that no $X_\alpha$ is monochromatic. The underlying space is a random red-blue colouring of $\Omega$. The bad event $B_\alpha$ is that $X_\alpha$ has been coloured monochromatically. Each $\mathbf{P}[B_\alpha] = 2^{-9} = p$. Each $A_\alpha$ overlaps at most $90$ other $A_\beta$, so $d = 90$. The Lovász local lemma gives the existence of a colouring.

The lemma was discovered by L. Lovász (see [a3] for an original application) in 1975. It ushered in a new era for the probabilistic method.

General case of the Lovász local lemma.

Let $B_\alpha$, $G$ be as above. If there exist an $x_\alpha \in (0,1)$ with $$ \mathbf{P}[B_\alpha] \le x_\alpha \prod (1-x_\beta)\,, $$ the product over those $\beta$ adjacent to $\alpha$, then $\wedge_I \bar B_\alpha \neq \emptyset$.

Application of the general case generally requires mild analytic skill in choosing the $x_a$.

The proof of the Lovász local lemma (in either case) requires only elementary (albeit ingenious) probability theory and takes less than a page.

A breakthrough in algorithmic implementation was given by J. Beck [a2] in 1991. He showed that in certain (though not all) situations where the Lovász local lemma guarantees the existence of an object, that object can be found by a polynomial-time algorithm. Proofs, applications and algorithmic implementation are explored in [a1] and elsewhere.

The acronym LLL is also used for the Lenstra–Lenstra–Lovász algorithm (see LLL basis reduction method).

References

[a1]	N. Alon, J. Spencer, "The probabilistic method" , Wiley (2000) (Edition: Second)
[a2]	J. Beck, "An algorithmic approach to the Lovász local lemma, I" , Random Structures and Algorithms , 2 (1991) pp. 343–365
[a3]	P. Erdős, L. Lovász, "Problems and results on 3-chromatic hypergraphs and some related questions" A. Hajnal (ed.) et al. (ed.) , Infinite and Finite Sets , North-Holland (1975) pp. 609–628