An Algorithmic Version of the Lovász Local Lemma

• Bruno Pasqualotto Cavalar USP

DOI: https://doi.org/10.5753/etc.2017.3189

Abstract

The Lovász Local Lemma (LLL) is a powerful tool for proving the existence of combinatorial objects which satisfy a given set of constraints. More precisely, given a finite collection of “bad” events A, the LLL gives sufficient conditions for the probability P [∩_A∈A Ā] to be positive. In a breakthrough by Moser and Tardos [Moser and Tardos 2010], an efficient algorithm for finding objects whose existence is guaranteed by the LLL was developed. This work surveys a few applications of the LLL in combinatorics and seeks to apply the Moser-Tardos algorithm in those problems.

References

Erdős, P. and Lovász, L. (1975). Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and finite sets, pages 609–627. North-Holland, Amsterdam.

Haeupler, B., Saha, B., and Srinivasan, A. (2011). New constructive aspects of the Lovász local lemma. J. ACM, 58(6):Art. 28, 28.

Hind, H., Molloy, M., and Reed, B. (1997). Colouring a graph frugally. Combinatorica, 17(4):469–482.

Hind, H., Molloy, M., and Reed, B. (1999). Total coloring with ∆ + poly(log ∆) colors. SIAM J. Comput., 28(3):816–821.

Leighton, T., Maggs, B., and Richa, A. W. (1999). Fast algorithms for finding O (congestion + dilation) packet routing schedules. Combinatorica, 19(3):375–401.

Molloy, M. and Reed, B. (1999). Further algorithmic aspects of the local lemma. In STOC ’98 (Dallas, TX), pages 524–529. ACM, New York.

Moser, R. A. and Tardos, G. (2010). A constructive proof of the general Lovász local lemma. J. ACM, 57(2):Art. 11, 15pp.