Gábor Tardos


A constructive proof of the Lovász Local Lemma

The Lovász Local Lemma is a powerful tool to non-constructively
prove the existence of combinatorial objects meeting a prescribed
collection of criteria. Among other applications it is also used in
combinatorial geometry, for example to show that certain multiple
coverings of the space covering each point a bounded number of times
split into several coverings. In his breakthrough paper Beck
demonstrated that a constructive variant of the lemma can be given
under certain more restrictive conditions. We give a new proof of the
lemma that gives a very simple and efficient algorithm to actually
find the object whose existence the lemma claims. This algorithmic
version does not require additional conditions to hold beyond the ones
required by the original lemma.

This is joint work with Robin Moser.