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.
Our second contribution is a technical idea concerning slack in the LLL criteria. This idea is a perfectly valid statement regarding the existential LLL as well, although we will exploit it algorithmically. One drawback of the forward-looking analysis is that it naturally leads to an exponential bound on the number of resamplings, unless there is some slack in the LLL criterion; this same issue arises in @cite_5 @cite_24 . Our idea eliminates the need for slack in the and criteria. We prove that, even if or are tight, we can instead perform our analysis using Shearer's criterion, which is never tight because it defines an open set. For example, consider the familiar case of LLL , and suppose that holds with equality, i.e., @math for all @math . We show that the conclusion of the LLL remains true even if each event @math actually had the larger probability @math . The proof of this fact crucially uses Shearer's criterion and it does not seem to follow from more elementary tools @cite_2 @cite_18 .
@cite_24 @cite_5 @cite_18 @cite_2
1810595280 2078116611 2051336598 131018274
The algorithm for Lovasz Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects that satisfy a system of constraints. We present an alternative probabilistic analysis of the algorithm that does not involve reconstructing the history of the algorithm from the witness tree. We apply our technique to improve the best known upper bound to acyclic chromatic index. Specifically we show that a graph with maximum degree Δ has an acyclic proper edge coloring with at most ⌈3.74(Δ − 1)⌉ + 1 colors, whereas the previously known best bound was 4(Δ − 1). The same technique is also applied to improve corresponding bounds for graphs with bounded girth. An interesting aspect of this application is that the probability of the "undesirable" events do not have a uniform upper bound, i.e. it constitutes a case of the asymmetric Lovasz Local Lemma. A folklore result uses the Lovasz local lemma to analyze the discrepancy of hypergraphs with bounded degree and edge size. We generalize this result to the context of real matrices with bounded row and column sums. Abstract A probability theorem, due to Lovasz, is used to derive lower bounds for various Ramsey functions. A short proof of the known result R(3, t) ⩾ ct 2 ( ln t) 2 is given.