Lovász local lemma

The Lovász - Local - Lemma is a lemma from probability theory. It generalizes the argument that the stochastic independence of events with positive probability a positive probability for the occurrence of all events implies, to situations in which not all events are independent. Its name is due to the fact that it is composed of local features into a global result. It is most commonly used in probabilistic approaches to perform proofs of existence. 1975, it was proved by László Lovász and Paul Erdős.

Statement of the lemma

Public version

Let be a set of events over an arbitrary probability space, so that each event is stochastically independent of all others except for one.

If real numbers exist, such that for all:

As follows:.

In many proofs of the following symmetric special case will be used.

Symmetric version

Let be a set of events over an arbitrary probability space, so that each event is stochastically dependent on at most other events.

If

As follows.

Example of use

Be a hypergraph such that each hyperedge contains at least nodes and intersects at most other hyperedges and. Then is 2- colorable.

Coloring the nodes of initially randomly, independently and uniformly distributed with two colors ( ie the probability that a node is, for example, red or blue is, respectively). Set for all hyperedges: Reversing now the symmetrical Local Lemma to the crowd. In this case the event is that all nodes have been colored in the same color of an edge. First, each event is stochastically dependent on, since each edge from a node shares at least by definition. By assumption: for all edges. On the other hand, each event is stochastically independent of, because the nodes were stained independently. Since, then:. So, that is: is 2- colorable.

In another version of the Lovász - Local - Lemma the request is sufficient. With this statement, followed by the 2- colorability for. It is then that.