Fetching the paper…

Reading the bibliography…

2009

A constructive proof of the general Lovasz Local Lemma

Moser, Robin A., Tardos, Gábor

Original
PDF
Post on X

Understand

The Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria.

In his breakthrough paper [Bec91], Beck demonstrated that a constructive variant can be given under certain more restrictive conditions.
Simplifications of his procedure and relaxations of its restrictions were subsequently exhibited in several publications [Alo91, MR98, CS00, Mos06, Sri08, Mos08].
In [Mos09], a constructive proof was presented that works under negligible restrictions, formulated in terms of the Bounded Occurrence Satisfiability problem.

A constructive proof of the general Lovasz Local Lemma · Around

Built on

Donald E. Knuth
1969
Earlier work this paper cites.
Paul Erdős and László Lovász
1975
Earlier work this paper cites.
Paul Erdős and Joel Spencer
1991
Earlier work this paper cites.
Jószef Beck
1991
Earlier work this paper cites.
Noga Alon
1991
Earlier work this paper cites.

Similar

Jan Kratochvíl and Petr Savický and Zsolt Tuza
1993
Cited alongside, same era.
Michael Molloy and Bruce Reed
1998
Cited alongside, same era.
Artur Czumaj and Christian Scheideler
2000
Cited alongside, same era.
Piotr Berman, Marek Karpinski, and Alexander D. Scott
2003
Cited alongside, same era.
Robin A. Moser
2006
Cited alongside, same era.

Then

Aravind Srinivasan
2008
Later among the works it cites.
Emo Welzl
2008
Later among the works it cites.
Robin A. Moser
Original
2008
Later among the works it cites.
Robin A. Moser
Original
2008
Later among the works it cites.
János Pach and Gábor Tardos
2009
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…