The Lovasz Local Lemma is a seminal result in probabilistic combinatorics. It gives a sufficient condition on a probability space and a collection of events for the existence of an outcome that simultaneously avoids all of those events. Finding such an outcome by an efficient algorithm has been an active research topic for decades. Breakthrough work of Moser and Tardos (2009) presented an efficient algorithm for a general setting primarily characterized by a product structure on the probability space. In this work we present an efficient algorithm for a much more general setting. Our main assumption is that there exist certain functions, called resampling oracles, that can be invoked to address the undesired occurrence of the events. We show that, in all scenarios to which the original Lovasz Local Lemma applies, there exist resampling oracles, although they are not necessarily efficient. Nevertheless, for essentially all known applications of the Lovasz Local Lemma and its generalizations, we have designed efficient resampling oracles. As applications of these techniques, we present new results for packings of Latin transversals, rainbow matchings and rainbow spanning trees.
Following this, Moser and Tardos @cite_29 showed that a similar algorithm will produce a state in @math , assuming the independent variable model and the criterion. This paper is primarily responsible for the development of witness trees, and proved the witness tree lemma'', which yields an extremely elegant analysis in the variable model. The witness tree lemma has further implications. For example, it allows one to analyze separately for each event its expected number of resamplings. Moser and Tardos also extended the variable model to incorporate a limited form of lopsidependency, and showed that their analysis still holds in that setting.
@cite_29
2109693504
The Lovasz Local Lemma discovered by Erdős and Lovasz in 1975 is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In 1991, Jozsef Beck was the first to demonstrate that a constructive variant can be given under certain more restrictive conditions, starting a whole line of research aimed at improving his algorithm's performance and relaxing its restrictions. In the present article, we improve upon recent findings so as to provide a method for making almost all known applications of the general Local Lemma algorithmic.