Lovász Local Lemma

The Lovász local lemma is a proposition from probability theory . It generalizes the argument that the stochastic independence of events with positive probability implies a positive probability for all events to occur to situations in which not all events are independent. Its name is based on the fact that it combines local properties into a global result. It is most commonly used in probabilistic approaches to prove existence. In 1975 it was proven by László Lovász and Paul Erdős .

Statement of the lemma

General version

Let be a set of events over an arbitrary probability space such that each event is stochastically independent of all events in each one . ${\displaystyle {\mathcal {E}}=\{A_{1},A_{2},\dots ,A_{n}\}}$ ${\displaystyle A_{i}}$ ${\displaystyle {\mathcal {D}}_{i}\subseteq {\mathcal {E}}}$

If real numbers exist such that for all true: ${\displaystyle x_{1},x_{2},\dots ,x_{n}\in [0,1)}$ ${\displaystyle i\in \{1,2,\dots ,n\}}$

${\displaystyle Pr(A_{i})\leq x_{i}\prod _{A_{k}\in {\mathcal {D}}_{i}}(1-x_{k})}$,

as follows: . ${\displaystyle Pr(\bigcap _{i=1}^{n}{\overline {A}}_{i})\geq \prod _{j=1}^{n}(1-x_{j})>0}$

In many proofs the following special symmetric case is used.

Symmetrical version

Let be a set of events over an arbitrary probability space such that each event is stochastically dependent on at most other events. ${\displaystyle {\mathcal {E}}=\{A_{1},A_{2},\dots ,A_{n}\}}$ ${\displaystyle {\mathcal {E}}}$ ${\displaystyle d}$

If

1. ${\displaystyle \forall i\in \{1,2,\dots ,n\}:Pr(A_{i})\leq p}$, where , ${\displaystyle p\in [0,1]}$
2. ${\displaystyle e\cdot p\cdot (d+1)\leq 1}$, ( Euler's number ) ${\displaystyle e}$

so follows . ${\displaystyle Pr(\bigcap _{i=1}^{n}{\overline {A}}_{i})>0}$

Application example

Let be a hypergraph such that every hyperedge contains at least nodes and intersects with at most further hyperedges and . Then is 2-colorable. ${\displaystyle {\mathcal {H}}}$ ${\displaystyle k}$ ${\displaystyle 2^{k-3}}$ ${\displaystyle k\geq 5}$ ${\displaystyle {\mathcal {H}}}$

Color the nodes from initially random, independent, and evenly distributed with two colors (i.e. the probability that a node is red or blue, for example, is each ). Set for all hyperedges : Now apply the symmetric local lemma to the set . It is the event that all nodes of an edge have been dyed in the same color. First of all, every event is stochastically dependent on , since every edge shares at least one node with by definition . According to the prerequisite: for all edges . On the other hand, every event is stochastically independent of , since the nodes were colored independently of each other. As is true: . So is , that is: is 2-colorable. ${\displaystyle {\mathcal {H}}}$ ${\displaystyle {\frac {1}{2}}}$ ${\displaystyle N_{e}:=\{f\in E({\mathcal {H}})|f\cap e\neq \emptyset \}}$ ${\displaystyle e\in E({\mathcal {H}})}$ ${\displaystyle {\mathcal {E}}:=\{A_{e}|e\in E({\mathcal {H}})\}}$ ${\displaystyle A_{e}}$ ${\displaystyle e}$ ${\displaystyle A_{e}}$ ${\displaystyle N_{e}}$ ${\displaystyle N_{e}}$ ${\displaystyle e}$ ${\displaystyle |N_{e}|\leq 2^{k-3}=:d}$ ${\displaystyle e\in E({\mathcal {H}})}$ ${\displaystyle A_{e}}$ ${\displaystyle \{A_{f}|f\in E({\mathcal {H}}),f\cap e=\emptyset \}}$ ${\displaystyle Pr(A_{e})\leq 2\left({\frac {1}{2}}\right)^{k}=2^{1-k}=:p}$ ${\displaystyle e\cdot p\cdot (d+1)<1}$ ${\displaystyle Pr\left(\bigcap _{e\in E({\mathcal {H}})}{\overline {A}}_{e}\right)>0}$ ${\displaystyle {\mathcal {H}}}$

In another version of the Lovász local lemma, the requirement is sufficient . With this statement, the 2-colorability also follows for . It then applies . ${\displaystyle 4\cdot p\cdot d\leq 1}$ ${\displaystyle k\geq 3}$ ${\displaystyle 4\cdot p\cdot d=4\cdot {\frac {2^{k-3}}{2^{k-1}}}=1}$

literature

• Michael Molloy; Bruce Reed: Graph Coloring and the Probabilistic Method . Springer, 2002, ISBN 3-540-42139-4 , pp. 221-229 .

Individual evidence

1. ↑ Noga Alon; Joel H. Spencer. The Probabilistic Method. 3rd edition, 2008. page 70
2. ↑ Michael Molloy; Bruce Reed. Graph Coloring and the Probabilistic Method . 2002, chapter 4