Namespaces
Variants
Actions

Difference between revisions of "Lovász local lemma"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Category:Combinatorics)
(LaTeX)
Line 1: Line 1:
 +
{{TEX|done}}
 +
 
''LLL''
 
''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.
 
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l1301101.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l1301102.png" />, be a finite family of  "bad"  events. A [[Graph|graph]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l1301103.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l1301104.png" /> is called a dependency graph for the events if each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l1301105.png" /> is mutually independent of those <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l1301106.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l1301107.png" /> not adjacent (cf. also [[Independence|Independence]]).
+
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.==
 
==Symmetric case of the Lovász local lemma.==
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l1301108.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l1301109.png" /> be as above. Suppose all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011010.png" />. Suppose all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011011.png" /> are adjacent to at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011012.png" /> other <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011013.png" />. Suppose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011014.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011015.png" />.
+
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, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011016.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011017.png" /> depends on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011018.png" /> of choices, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011019.png" /> are adjacent when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011020.png" /> overlap.
+
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.===
 
===Example.===
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011022.png" />, be sets of size ten in some universe <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011023.png" />, where every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011024.png" /> lies in at most ten such sets. Then there is a red-blue colouring of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011025.png" /> so that no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011026.png" /> is monochromatic. The underlying space is a random red-blue colouring of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011027.png" />. The bad event <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011028.png" /> is that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011029.png" /> has been coloured monochromatically. Each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011030.png" />. Each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011031.png" /> overlaps at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011032.png" /> other <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011033.png" />, so <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011034.png" />. The Lovász local lemma gives the existence of a colouring.
+
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 [[#References|[a3]]] for an original application) in 1975. It ushered in a new era for the probabilistic method.
 
The lemma was discovered by L. Lovász (see [[#References|[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.==
 
==General case of the Lovász local lemma.==
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011035.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011036.png" /> be as above. If there exist an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011037.png" /> with
+
Let $B_\alpha$, $G$ be as above. If there exist an $x_\alpha \in (0,1)$ with
 
+
$$
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011038.png" /></td> </tr></table>
+
\mathbf{P}[B_\alpha] \le x_\alpha \prod (1-x_\beta)\,,
 
+
$$
the product over those <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011039.png" /> adjacent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011040.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011041.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l130/l130110/l13011042.png" />.
+
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|probability theory]] and takes less than a page.
+
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 [[#References|[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 [[#References|[a1]]] and elsewhere.
 
A breakthrough in algorithmic implementation was given by J. Beck [[#References|[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 [[#References|[a1]]] and elsewhere.
  
The acronym LLL is also used for the Lenstra–Lenstra–Lovász algorithm (see [[LLL basis reduction method|LLL basis reduction method]]).
+
The acronym LLL is also used for the Lenstra–Lenstra–Lovász algorithm (see [[LLL basis reduction method]]).
  
 
====References====
 
====References====

Revision as of 19:34, 18 December 2014


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
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