Lovász Local Lemma (symmetric, general/asymmetric, and algorithmic/random-recoloring variants) — probabilistic existence when bad events are individually non-negligible but sparsely dependent

Statement

General (asymmetric) Lovász Local Lemma. Let $A_1,\dots,A_n$ be events in a probability space, each with an associated *dependency graph* $\Gamma$: event $A_i$ is mutually independent of the collection of all $A_j$ with $j\notin \Gamma(i)\cup\{i\}$ (i.e. $A_i$ may only be dependent on its "neighbors" $\Gamma(i)$). If there exists an assignment of reals $x:\{A_1,\dots,A_n\}\to[0,1)$ such that for every $i$, $$\Pr[A_i] \le x(A_i)\prod_{j\in\Gamma(i)}\big(1-x(A_j)\big),$$ then $$\Pr\Big[\bigwedge_{i=1}^n \overline{A_i}\Big] \ge \prod_{i=1}^n\big(1-x(A_i)\big) > 0,$$ i.e. with strictly positive probability none of the bad events $A_i$ occurs — so an outcome avoiding all of them exists (en.wikipedia.org/wiki/Lovász_local_lemma, WebFetch-verified).

Symmetric form (the version almost always quoted/used). If every $\Pr[A_i]\le p$ and every event is dependent on at most $d$ others (i.e. $|\Gamma(i)|\le d$ for all $i$), then the criterion $$e\,p\,(d+1) \le 1$$ (equivalently $ep(d+1)\le1$, sometimes stated as $4pd\le1$ in an easier-to-prove weaker form) suffices to guarantee $\Pr[\bigwedge\overline{A_i}]>0$. (Set $x(A_i)=1/(d+1)$ for all $i$ in the general form and check the inequality using $(1-1/(d+1))^d \ge 1/e$.)

History. First proved by Paul Erdős and László Lovász in 1975: P. Erdős, L. Lovász, "Problems and results on 3-chromatic hypergraphs and some related questions," in *Infinite and Finite Sets* (Colloq. Math. Soc. János Bolyai 10), North-Holland, 1975 — introduced to attack 3-colorability of hypergraphs. The name honors both; textbook treatments (Alon–Spencer, *The Probabilistic Method*, Ch. 5) present it as one of the core "beyond a union bound" probabilistic tools.

Algorithmic (constructive) Lovász Local Lemma — Moser–Tardos, 2010. The original 1975 proof is purely existential (non-constructive); Robin A. Moser and Gábor Tardos gave an efficient randomized *algorithm* that actually finds an outcome avoiding all bad events, under essentially the same hypotheses (R. A. Moser, G. Tardos, "A constructive proof of the general Lovász Local Lemma," J. ACM 57(2) (2010)). Setup: a finite set $P$ of mutually independent random variables; a finite set $A$ of "bad" events, each determined by (a function of) some subset of variables in $P$; a dependency structure $\Gamma(A)$ (events sharing a variable, or otherwise declared dependent). If there is $x:A\to(0,1)$ with $\Pr[A]\le x(A)\prod_{B\in\Gamma(A)}(1-x(B))$ for every $A$ (the same LLL criterion), the algorithm is:

1. Sample all variables in $P$ independently at random (an initial assignment). 2. While some event $A\in\mathcal A$ is currently satisfied ("violated" — a bad event holding), pick any one such $A$ and resample (redraw independently) all variables that $A$ depends on. 3. Terminate and return the assignment once no bad event holds.

Theorem (Moser–Tardos). This process terminates almost surely, and the expected number of times any particular event $A$ is resampled is at most $x(A)/(1-x(A))$; hence the expected total number of resampling steps is at most $\sum_{A\in\mathcal A} x(A)/(1-x(A))$ — polynomial in the problem size whenever the LLL criterion holds with reasonable slack (en.wikipedia.org/wiki/Algorithmic_Lovász_local_lemma, WebFetch-verified). Moser and Tardos received the 2020 Gödel Prize for this result.

Proof idea (entropy compression). The algorithm's execution is encoded as a *log* (the sequence of which event got resampled, plus the random bits used at each step). One shows this log can always be losslessly *reconstructed* from (a) the final variable assignment and (b) the sequence of resampled-event *names* alone, via a "witness tree" argument tracking causal dependencies between resampling steps. If the algorithm ran for $T$ steps, the log carries $T$ "records," but under the LLL numeric criterion each record can be shown to carry strictly less entropy (information) than a single random resampling step actually injects — a counting/compression contradiction unless $T$ is small. This is the entropy-compression method, later abstracted (Tao's blog exposition, Fortnow's, and others) as a proof technique in its own right beyond the LLL. See also the lopsided LLL (dependency relaxed to a one-sided/positive-correlation condition, used e.g. for random Latin transversals) and the cluster-expansion lemma, both surveyed in Sason, "The Lovász Local Lemma: Foundations and Applications," arXiv:2603.07245 (2026).

Random-recoloring / algorithmic variant for hypergraph coloring (Kozik–Shabanov). A specialized algorithmic-LLL descendant used directly in Erdős-problem territory: J. Kozik, D. Shabanov, "Improved algorithms for colorings of simple hypergraphs and applications," J. Combin. Theory Ser. B (2016) 312–332 (arXiv:1409.6921) gives a Moser–Tardos-style *random-recoloring* algorithm for properly $r$-colouring simple hypergraphs (bounding uniformity/degree trade-offs), yielding the current-best van der Waerden lower bound $W(k,r) > c\cdot r^{k-1}$ (so $W(k)\gg 2^k$ for $r=2$) — a case where making the LLL constructive, not just its existence guarantee, is what produces the applicable coloring.

Facts

- The "escalation" step beyond the union bound / alteration method. A plain union bound (Boole's inequality) needs $\sum_i \Pr[A_i] < 1$ — it forces *every individual* bad-event probability toward $0$ as the number of events grows. The LLL instead only needs each $\Pr[A_i]$ small relative to its local dependency degree $d$ ($ep(d+1)\le1$), so it tolerates *far more numerous* and *individually much larger*-probability bad events, provided the dependency structure is sparse. This is precisely why LLL constructions beat plain alteration/deletion constructions by better multiplicative constants in Ramsey-type lower bounds: compare Erdős's 1947 union-bound diagonal Ramsey constant $1/(\sqrt2\,e)$ to Spencer's 1975 LLL-based $\sqrt2/e$ (wiki/problems/1029.md) — a factor-of-2 gain purely from swapping the tail-bound tool. - Canonical Ramsey-number applications. Spencer 1975 (J. Combin. Theory Ser. A 18, 108–115) — diagonal $R(k,k)\ge(1+o(1))\frac{\sqrt2}{e}k2^{k/2}$, unimproved in *order* since 1975 (wiki/problems/1029.md); Spencer 1977 (Discrete Math. 20, 69–76) — off-diagonal $R(C_4,K_n)\gg n^{3/2}/(\log n)^{3/2}$ (wiki/problems/159.md). - Canonical van der Waerden / arithmetic-progression coloring applications. Szabó 1990, symmetric LLL, $W(k)\ge 2^k/k^\varepsilon$ — the best-known *general* lower-bound order for the diagonal van der Waerden number, unimproved since 1990 (wiki/problems/138.md); Kozik–Shabanov 2016 (arXiv:1409.6921), *algorithmic* random-recoloring LLL, same order with better constants and multicolor form $W(k,r)>c\cdot r^{k-1}$; Ji Ho Bae 2026 (arXiv:2604.20588) and independently Fox–Hunter 2026 (arXiv:2606.02541) resolve the *canonical* van der Waerden problem (Erdős's #190, $H(k)^{1/k}/k\to\infty$) by applying the symmetric LLL with the colour count $r$ allowed to grow with $k$ (rather than fixed at $r=2$) — the same base LLL bound $W(r,k)\gg r^{k-1}/k$, but exploited along a different asymptotic axis than the still-open fixed-$r=2$ diagonal question (wiki/problems/190.md, wiki/problems/138.md); Fox–Hunter's 3-color-specific super-exponential construction (arXiv:2606.02541, Corollary 3.3) uses the LLL as an inner gadget converting a sparse "AP-hitting set" into a genuine local no-monochromatic-domination coloring, then iterates via a random-shifted-product amplification (wiki/problems/three-color-vdw-super-exponential.md). - k-SAT satisfiability. The classical LLL application (surveyed widely, e.g. Sason arXiv:2603.07245): if every clause of a k-CNF formula shares variables with at most $d$ other clauses, and each clause has $2^{-k}$ probability of being falsified under a uniform random assignment, the symmetric LLL criterion $e\cdot 2^{-k}(d+1)\le1$ certifies satisfiability whenever $d \lesssim 2^k/e$ — independent of the *total* number of clauses/variables, unlike a union bound. - Covering-systems / distortion-method application. The resolution of Erdős's minimum-modulus covering-system problem (Hough 2015, refined by Balister–Bollobás–Morris–Sahasrabudhe–Tiba's "distortion method," arXiv:2211.01417) combines an LLL-flavored "bad events = residues left uncovered, avoid them simultaneously" obstruction with staged second-moment/distortion tracking, rather than a pure union bound (wiki/problems/2.md, wiki/concepts/distortion-method.md). - Lopsided LLL and cluster-expansion refinements relax the strict-independence dependency-graph requirement to a weaker "negative/positive correlation" condition (useful e.g. for random Latin transversals and permutation-avoidance problems) and sharpen the numeric threshold beyond $ep(d+1)\le1$ in some regimes — surveyed in Sason, arXiv:2603.07245 (2026), alongside the Moser–Tardos algorithmic framework and entropy compression. - Relation to the semi-random / Rödl-nibble method. The nibble (Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings) iterates *many* small random-then-repair rounds with per-round concentration; the LLL instead certifies existence (or, algorithmically, finds) a *single* draw avoiding all bad events at once, provided the dependency structure is sparse — they are complementary tools for the same "random object with too many entangled constraints" problem shape, and some modern proofs (e.g. the AKS dense Sidon-sequence bound, wiki/problems/ajtai-komlos-szemeredi-dense-infinite-sidon-sequence.md) use LLL-type concentration control *inside* nibble rounds.

Technique

WHEN it applies. Reach for the Lovász Local Lemma when: 1. You have a finite (or countable, via compactness) family of "bad events" $A_1,\dots,A_n$ in some natural random model (a random coloring, random assignment of colors/labels, random recoloring of a hypergraph, a random 2-coloring of arithmetic-progression elements, etc.) whose simultaneous avoidance would certify the combinatorial structure you want. 2. Each bad event, on its own, has probability that is not going to $0$ fast enough for a plain union bound to work directly (unlike the alteration method, The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs, which needs $\sum\Pr[A_i]=o(1)$) — but each bad event is only "entangled" with (probabilistically dependent on) a bounded, small number $d$ of the other bad events (e.g. because it only involves a bounded-size subset of the shared random variables/coordinates, like one arithmetic progression's set of positions, or one clause's set of Boolean variables). 3. The numeric trade-off $ep(d+1)\le1$ (or the general asymmetric criterion) can be satisfied by tuning free parameters of the construction (density of a random subset, number of colors, size of a coloring palette, etc.) — this tuning step is almost always the crux of applying LLL to a *new* problem.

WHY it works (the mechanism). The union bound is "pessimistic" because it assumes the worst case: that avoiding $A_i$ could be *anti-correlated* with avoiding every other $A_j$, forcing you to make every individual $\Pr[A_i]$ vanishingly small to survive $n$-many union-bound terms. The Local Lemma instead exploits *sparsity of dependence*: if $A_i$ is mutually independent of all-but-$d$ of the other events, then conditioning on avoidance of "far away" events cannot hurt $A_i$'s own avoidance probability much, and an inductive/recursive argument (the standard textbook proof: bound $\Pr[A_i \mid \bigwedge_{j\in S}\overline{A_j}]$ by induction on $|S|$, splitting $S$ into $\Gamma(i)\cap S$ and the rest) shows the *whole* conjunction $\bigwedge\overline{A_i}$ retains positive probability as long as the local numeric criterion holds — no matter how large $n$ is. This is the essential leverage: **LLL trades "small enough that a union bound survives $n$ terms" for "small enough relative to $d$, the *local* dependency degree, regardless of $n$."** The Moser–Tardos algorithmic version makes this constructive by literally performing local repairs (resampling only the variables of a currently-violated event) and using an entropy-compression counting argument, rather than an inductive conditioning argument, to bound the expected work — swapping a purely existential inductive proof for an operational, terminating random process with the same asymptotic reach.

The reusable recipe

1. Set up the random model (random coloring of $[N]$, random Boolean assignment, random recoloring of hypergraph vertices, etc.) and identify the "bad events" whose simultaneous avoidance is exactly the combinatorial structure sought (e.g. "this arithmetic progression is monochromatic," "this clause is falsified," "this hyperedge is monochromatic"). 2. Bound $p=\max_i\Pr[A_i]$ — usually an elementary calculation (e.g. $\Pr[\text{AP monochromatic under uniform random }r\text{-coloring}]=r^{1-k}$ for a $k$-term AP). 3. Bound $d=\max_i|\Gamma(i)|$, the number of *other* bad events that share a random variable (or are otherwise declared dependent) with $A_i$ — usually a counting argument over how many other structures (other APs, other clauses, other hyperedges) can intersect a fixed one. 4. Check/tune parameters so that $ep(d+1)\le1$ (symmetric) or find a valid $x(\cdot)$ assignment satisfying the general asymmetric criterion. This is where the problem-specific optimization happens — e.g. choosing how many colors $r$, or how sparse a "hitting set" gadget must be, or letting $r$ grow with $k$ (as in the #190 canonical-vdW resolution) to make the criterion hold in a regime a fixed-parameter version could not reach. 5. Conclude existence (classical LLL) — a valid coloring/assignment/structure exists with positive probability — or run the Moser–Tardos algorithm (algorithmic LLL) if an efficient constructive witness, not just an existence proof, is needed; verify the expected-resampling bound $\sum x(A)/(1-x(A))$ is polynomial for the application at hand. 6. If a single application of the numeric criterion falls short of the target parameter regime (e.g. you need a bound that beats what fixed-$d$/fixed-$p$ LLL can give), consider: (a) the lopsided LLL if the dependency structure is one-sidedly (not mutually) correlated; (b) using LLL as an *inner gadget* inside a larger iterated/amplification construction (as in the Fox–Hunter random-shifted-product 3-color van der Waerden construction, or nibble-style repeated rounds); (c) letting a *free parameter grow with the problem size* (the #190 trick: colour count $r\to\infty$ with $k$) rather than treating it as fixed.

HOW to use this to prove new things (recombination guidance for a solver). - If a problem asks for a lower bound on a Ramsey-type / coloring-avoidance / covering-avoidance quantity, and the natural union-bound (alteration-method) argument gives a bound that "feels" a constant factor or so too weak, first check whether the bad events in that argument are only *locally* (not globally) dependent — if so, LLL will typically improve the constant (as in Spencer's factor-of-$\sqrt2$ Ramsey gain) without changing the construction's basic shape. - If the problem is about *constructing* (not just proving existence of) a combinatorial witness — e.g. an actual satisfying assignment, an actual coloring — and a plain existential LLL argument would suffice for existence, check whether the Moser–Tardos algorithmic form applies (same numeric criterion, plus a well-defined resampling procedure): this upgrades an existence proof to a polynomial-expected-time constructive algorithm essentially for free. - If a fixed-parameter symmetric-LLL argument gives an order-of-magnitude bound that has been "stuck" for decades (e.g. $W(k)\ge2^k/k^\varepsilon$ since Szabó 1990, or $R(k,k)\ge(\sqrt2/e)k2^{k/2}$ since Spencer 1975 — both still current per wiki/problems/138.md and wiki/problems/1029.md), the productive escalation paths documented in this wiki are: (a) find an unexploited free parameter to let grow with the problem size (the #190 trick), (b) make the LLL *algorithmic/random-recoloring* rather than purely existential to extract better constants via more careful degree/uniformity trade-offs (Kozik–Shabanov's gain over Szabó), or (c) replace LLL with a structurally different construction entirely (pseudorandom/geometric constructions, as in the recent off-diagonal Ramsey breakthroughs, wiki/problems/1029.md) when LLL's *order* itself appears to be the bottleneck rather than its constant. - LLL, like alteration and the nibble, is a lower-bound / existence technique — it says nothing about matching upper bounds; pair it with a genuinely different (extremal, sieve-theoretic, or algebraic) argument if the target open problem is about tightness or impossibility.

Related

- The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs — the coarser, union-bound-only sibling technique that LLL supersedes when bad events are sparsely (not just individually-rare) dependent; that page's own text explicitly frames LLL as "permits bad events with individually much larger probability, provided they are sparsely dependent." - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the iterated, many-small-rounds sibling; complementary rather than competing, and sometimes composed with LLL-type concentration control inside individual nibble rounds. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — a different escalation from plain first-moment/union-bound arguments (variance/Chebyshev rather than dependency-sparsity); a natural alternative to try when LLL's dependency-degree bound $d$ is not controllable. - Distortion method (Hough; Balister–Bollobás–Morris–Sahasrabudhe–Tiba) for covering-system impossibility bounds — the staged-revelation covering-system technique that combines an LLL-flavored "avoid all uncovered-residue bad events" obstruction with second-moment distortion tracking (used to resolve Erdős's minimum-modulus covering-system problem). - Erdős #1029 — polynomial-factor lower bound $R(k)/(k2^{k/2})\\to\\infty$ — diagonal Ramsey number lower bound $R(k,k)\ge(1+o(1))(\sqrt2/e)k2^{k/2}$; Spencer 1975's symmetric-LLL improvement over Erdős's 1947 union-bound constant, unimproved in order since. - Erdős #159 — polynomial improvement to R(C4,Kn) upper bound — $R(C_4,K_n)$ lower bound via Spencer 1977's LLL argument. - Erdős #190 — canonical Ramsey growth rate H(k)^{1/k}/k → ∞ (SOLVED) — SOLVED (2026): canonical van der Waerden problem $H(k)^{1/k}/k\to\infty$, resolved via symmetric LLL with growing colour count (Bae arXiv:2604.20588; independently Fox–Hunter arXiv:2606.02541 §6). - Erdős #138 — does W(k)^{1/k} → ∞ for van der Waerden numbers? — OPEN: fixed-colour ($r=2$) diagonal van der Waerden \$500 problem $W(k)^{1/k}\to\infty$; best lower-bound order $W(k)\ge2^k/k^\varepsilon$ still from Szabó's 1990 symmetric LLL / Kozik–Shabanov's 2016 algorithmic-LLL argument, unimproved since — the clearest "LLL got us this far, no further" case study in this wiki.