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 , , be a finite family of "bad" events. A graph on is called a dependency graph for the events if each is mutually independent of those with not adjacent (cf. also Independence).

Symmetric case of the Lovász local lemma.

Let , be as above. Suppose all . Suppose all are adjacent to at most other . Suppose . Then .

Here, the number of events, , may be arbitrarily high, 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 depends on a set of choices, and are adjacent when overlap.

Example.

Let , , be sets of size ten in some universe , where every lies in at most ten such sets. Then there is a red-blue colouring of so that no is monochromatic. The underlying space is a random red-blue colouring of . The bad event is that has been coloured monochromatically. Each . Each overlaps at most other , so . 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 , be as above. If there exist an with

the product over those adjacent to , then .

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

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