View source for 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 <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]]).

==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" />.

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.

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

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

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

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" />.

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" />.

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.

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]]).

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  N. Alon,   J. Spencer,   "The probabilistic method" , Wiley  (2000)  (Edition: Second)</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Beck,   "An algorithmic approach to the Lovász local lemma, I" , ''Random Structures and Algorithms'' , '''2'''  (1991)  pp. 343–365</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  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</TD></TR>
</table>

[[Category:Combinatorics]]