Namespaces
Variants
Actions

Lovász local lemma

From Encyclopedia of Mathematics
Revision as of 07:54, 26 March 2012 by Ulf Rehmann (talk | contribs) (moved Lovasz local lemma to Lovász local lemma over redirect: accented title)
Jump to: navigation, search

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
How to Cite This Entry:
Lovász local lemma. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Lov%C3%A1sz_local_lemma&oldid=33977
This article was adapted from an original article by Joel Spencer (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article