40.07.04 · combinatorics / probabilistic-method

The Lovász Local Lemma and the Moser-Tardos Algorithm

shipped3 tiersLean: none

Anchor (Master): Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 5 and §5.6-5.7 (the Moser-Tardos algorithmic local lemma, the lopsided version); Erdős-Lovász 1975 *Colloq. Math. Soc. János Bolyai* 10 (Infinite and Finite Sets) (the original lemma); Moser-Tardos 2010 *J. ACM* 57 (the constructive proof via witness trees / entropy compression); Shearer 1985 *Combinatorica* 5 (the optimal lattice-gas / independence-polynomial bound)

Intuition Beginner

The first-moment method proves a good object exists when the average number of flaws is below one. But often there are so many possible flaws that their average is enormous — thousands of bad spots on average — and the first moment says nothing useful. Yet you may still feel the object should exist, because each flaw involves only a few ingredients, and flaws far apart in the structure have nothing to do with one another. The Lovász Local Lemma turns that feeling into a proof.

Here is the idea. List all the bad events you want to avoid. Make each one rare on its own, with probability at most some small $p$ . Now suppose each bad event is tangled up with only a few others — it shares ingredients with at most $d$ of them — and is otherwise completely independent of the rest. The lemma says: if rarity beats local crowding, by the clean rule that $p$ times about $d$ stays below a fixed budget, then with positive probability every single bad event is avoided at once. You do not need the average flaw count below one; you only need each flaw rare and each flaw lonely.

The second half of the story is that you can actually find the good object, not just know it exists. Start with a random guess. Whenever some bad event is currently happening, locally re-roll just the ingredients it touches, and repeat. This patient "fix the conflict in front of you" loop stops quickly, leaving a configuration with no bad events left.

Visual Beginner

Picture each bad event as a dot, and draw a line between two dots when those two events share an ingredient and so can influence each other. This picture is the dependency graph. A dot with few lines is a bad event that is nearly independent of everything; a dot with many lines is heavily entangled. The local lemma cares only about the largest number of lines at any dot — the local crowding $d$ — not about how many dots there are in total. A million lonely dots, each touching at most three others, are all avoidable together.

Quantity	Meaning	Local-lemma role
$p$	how rare each bad event is	smaller is better
$d$	most neighbours any event has	the local crowding
budget $e \times p \times (d + 1)$	rarity versus crowding	must stay at most $1$

The table is the whole criterion: keep the product $e \times p \times (d + 1)$ at or below $1$ , and a flawless configuration is guaranteed to exist.

Worked example Beginner

Suppose you have a long list of logical clauses, and you want one true/false setting of the variables that satisfies all of them. Each clause is a small demand on, say, $k = 3$ variables; a clause is "broken" by a random coin-flip setting exactly when all $3$ of its variables come out the one wrong way. We will see when a satisfying setting must exist.

Step 1. Find how rare one broken clause is. A clause of $3$ variables is broken only by one specific combination out of the $2 \times 2 \times 2 = 8$ equally likely settings of its three variables. So the chance a fixed clause is broken is $p = 1/8$ .

Step 2. Count local crowding. Say each clause shares a variable with at most $d$ other clauses. Two clauses can conflict only when they share a variable, so $d$ is the largest number of clause-neighbours any clause has.

Step 3. Apply the budget rule $e \times p \times (d + 1) \leq 1$ . Using $e$ about $2.718$ and $p = 1/8$ , the rule reads $2.718 \times \frac{1}{8} \times (d + 1) \leq 1$ , that is $(d + 1) \leq 8/2.718 \approx 2.94$ . So $d + 1$ can be as large as $2$ , giving $d = 1$ .

Step 4. Read off the guarantee. If every clause shares variables with at most $d = 1$ other clause, the budget holds and a satisfying setting is guaranteed to exist — no matter how many clauses there are in total.

What this tells us: rarity ( $p = 1/8$ ) and crowding ( $d$ ) trade off through one clean inequality, and the total number of clauses never enters. For $3$ -variable clauses the honest threshold grows like $2^{3} = 8$ neighbours once the constant $e$ is handled sharply; the rough hand-count here keeps the arithmetic plain.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $A_{1}, \dots, A_{n}$ are events on a common probability space, thought of as the bad events one wishes to avoid simultaneously; the goal is to show $Pr [⋂_{i} \overline{A_{i}}] > 0$ . Basic probability — conditional probability, independence of families of events — is imported from the probability units $37.0 *$ and applied here, not reproved.

Definition (dependency graph). A graph $D$ on vertex set ${1, \dots, n}$ is a dependency graph for the events $A_{1}, \dots, A_{n}$ if for each $i$ the event $A_{i}$ is mutually independent of the family ${A_{j} : (i, j) \in / E (D)}$ — that is, $A_{i}$ is independent of every event built from the $A_{j}$ with $j$ not adjacent to $i$ . Write $Γ (i) = {j : (i, j) \in E (D)}$ for the neighbourhood; the events outside $Γ (i) \cup {i}$ exert no influence on $A_{i}$ .

The general (asymmetric) Lovász Local Lemma. Suppose $D$ is a dependency graph for $A_{1}, \dots, A_{n}$ and there exist reals $x_{1}, \dots, x_{n} \in [0, 1)$ with $$ \Pr[A_i] ;\le; x_i \prod_{j \in \Gamma(i)} (1 - x_j) \qquad \text{for every } i. $$ Then $$ \Pr\Big[\bigcap_{i=1}^{n} \overline{A_i}\Big] ;\ge; \prod_{i=1}^{n} (1 - x_i) ;>; 0 , $$ so with positive probability none of the bad events occurs ^{[Alon-Spencer Ch. 5]}. The weights $x_{i}$ are a free parameter chosen per application; the inequality says each event must be rarer than a budget discounted by the weights on its neighbours.

The symmetric Lovász Local Lemma. If each $A_{i}$ has $Pr [A_{i}] \leq p$ and the dependency graph has maximum degree at most $d$ (each event mutually independent of all but at most $d$ others), and $$ e,p,(d + 1) \le 1 , $$ then $Pr [⋂_{i} \overline{A_{i}}] > 0$ . This follows from the general form by setting every $x_{i} = 1/ (d + 1)$ and using $(1 - 1/ (d + 1))^{d} > 1/ e$ .

The notation $Γ (i)$ , $\overline{A_{i}}$ , $Pr [\cdot ∣ \cdot]$ , the dependency graph $D$ , and the weights $x_{i}$ are registered in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

"A dependency graph records all statistical correlation." It records enough independence: $A_{i}$ must be independent of the joint behaviour of all non-neighbours, not merely pairwise uncorrelated. Pairwise independence does not suffice; mutual independence of the complement family is the requirement.
"The symmetric form needs $e p d \leq 1$ ." The correct factor is $d + 1$ , not $d$ : an event is counted among its own "forbidden" set, so the budget is $e p (d + 1) \leq 1$ . Dropping the $+ 1$ overstates how much crowding is tolerated.
" $x_{i}$ must equal $Pr [A_{i}]$ ." The $x_{i}$ are slack variables, not the probabilities; one needs only $Pr [A_{i}] \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j})$ , and choosing $x_{i}$ a little above $Pr [A_{i}]$ to leave room is the standard move. The conclusion $\prod (1 - x_{i})$ is then a valid lower bound on the survival probability.
"Positive probability means a large fraction." The bound $\prod (1 - x_{i})$ is typically exponentially small; the lemma is an existence statement, and a positive—however tiny—probability is exactly what existence requires.

Key theorem with proof Intermediate+

The signature result is the general local lemma itself; its applications to $k$ -SAT and hypergraph colouring follow as corollaries. The proof is the classical conditional-probability induction of Erdős and Lovász ^{[Erdős-Lovász 1975]}.

Theorem (general Lovász Local Lemma). Let $A_{1}, \dots, A_{n}$ have dependency graph $D$ , and let $x_{1}, \dots, x_{n} \in [0, 1)$ satisfy $Pr [A_{i}] \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j})$ for all $i$ . Then for every $i$ and every subset $S \subseteq {1, \dots, n} ∖ {i}$ , $$ \Pr\Big[A_i ,\Big|, \bigcap_{j \in S} \overline{A_j}\Big] ;\le; x_i , $$ and consequently $Pr [⋂_{i} \overline{A_{i}}] \geq \prod_{i} (1 - x_{i}) > 0$ .

Proof. The conditional bound is proved by induction on $∣ S ∣$ . For $S = \emptyset$ , $Pr [A_{i}] \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j}) \leq x_{i}$ since each factor is at most $1$ . For the inductive step, split $S = S_{1} \cup S_{2}$ where $S_{1} = S \cap Γ (i)$ are the neighbours of $i$ in $S$ and $S_{2} = S ∖ Γ (i)$ the non-neighbours. Write the conditional probability as a ratio, $$ \Pr\Big[A_i ,\Big|, \bigcap_{j \in S} \overline{A_j}\Big] = \frac{\Pr\big[A_i \cap \bigcap_{j \in S_1}\overline{A_j} ,\big|, \bigcap_{k \in S_2}\overline{A_k}\big]} {\Pr\big[\bigcap_{j \in S_1}\overline{A_j} ,\big|, \bigcap_{k \in S_2}\overline{A_k}\big]} . $$ Bound the numerator from above. Dropping the conditioning on $⋂_{j \in S_{1}} \overline{A_{j}}$ inside the numerator and using that $A_{i}$ is mutually independent of ${A_{k} : k \in S_{2}}$ (as $S_{2} \cap Γ (i) = \emptyset$ ), $$ \Pr\Big[A_i \cap \bigcap_{j \in S_1}\overline{A_j} ,\Big|, \bigcap_{k \in S_2}\overline{A_k}\Big] \le \Pr\Big[A_i ,\Big|, \bigcap_{k \in S_2}\overline{A_k}\Big] = \Pr[A_i] \le x_i \prod_{j \in \Gamma(i)}(1 - x_j). $$

Now bound the denominator from below. Enumerate $S_{1} = {j_{1}, \dots, j_{r}}$ and expand by the chain rule, $$ \Pr\Big[\bigcap_{\ell=1}^{r}\overline{A_{j_\ell}} ,\Big|, \bigcap_{k \in S_2}\overline{A_k}\Big] = \prod_{\ell=1}^{r}\Pr\Big[\overline{A_{j_\ell}} ,\Big|, \bigcap_{m < \ell}\overline{A_{j_m}} \cap \bigcap_{k \in S_2}\overline{A_k}\Big] \ge \prod_{\ell=1}^{r}(1 - x_{j_\ell}), $$ where each factor uses the induction hypothesis on a conditioning set of size $< ∣ S ∣$ to give $Pr [A_{j_{ℓ}} ∣ \dots] \leq x_{j_{ℓ}}$ , hence $Pr [\overline{A_{j_{ℓ}}} ∣ \dots] \geq 1 - x_{j_{ℓ}}$ . Since $S_{1} \subseteq Γ (i)$ , the product $\prod_{ℓ} (1 - x_{j_{ℓ}})$ is a sub-product of $\prod_{j \in Γ (i)} (1 - x_{j})$ , and all factors lie in $(0, 1]$ , so the denominator is at least $\prod_{j \in Γ (i)} (1 - x_{j})$ . Dividing, $$ \Pr\Big[A_i ,\Big|, \bigcap_{j \in S}\overline{A_j}\Big] \le \frac{x_i \prod_{j \in \Gamma(i)}(1 - x_j)}{\prod_{j \in \Gamma(i)}(1 - x_j)} = x_i . $$

Finally, by the chain rule over all $n$ events, $$ \Pr\Big[\bigcap_{i=1}^{n}\overline{A_i}\Big] = \prod_{i=1}^{n}\Pr\Big[\overline{A_i} ,\Big|, \bigcap_{m < i}\overline{A_m}\Big] \ge \prod_{i=1}^{n}(1 - x_i) > 0, $$ each factor bounded below using the conditional estimate just proved. $□$

Corollary ( $k$ -SAT). Let $Φ$ be a $k$ -CNF formula in which every clause shares a variable with at most $d$ other clauses. If $e (d + 1) \leq 2^{k}$ , then $Φ$ is satisfiable. Proof. Assign each variable true/false by an independent fair coin. For clause $C$ let $A_{C}$ be the event that $C$ is unsatisfied; a $k$ -clause is violated by exactly one of the $2^{k}$ settings of its variables, so $Pr [A_{C}] = 2^{- k} =: p$ . Two clause-events are dependent only when the clauses share a variable, so the dependency degree is at most $d$ . The hypothesis $e (d + 1) \leq 2^{k}$ is $e p (d + 1) \leq 1$ ; the symmetric local lemma gives $Pr [⋂_{C} \overline{A_{C}}] > 0$ , so a satisfying assignment exists. $□$

Corollary (hypergraph 2-colouring / property B). A $k$ -uniform hypergraph in which every edge meets at most $d$ others is 2-colourable (property B) whenever $e (d + 1) \leq 2^{k - 1}$ . Proof. Colour each vertex red/blue independently and uniformly. For edge $f$ let $A_{f}$ be the event that $f$ is monochromatic; $Pr [A_{f}] = 2 \cdot 2^{- k} = 2^{1 - k}$ , and $A_{f}$ depends only on edges sharing a vertex with $f$ , at most $d$ of them. Then $e 2^{1 - k} (d + 1) \leq 1$ is $e (d + 1) \leq 2^{k - 1}$ , and the symmetric form gives a proper 2-colouring. $□$

Bridge. The local lemma builds toward every existence proof where the first moment is hopeless because there are too many bad events: it replaces the global demand "expected defects below one" with the local pair "each defect rare, each defect lonely", and the foundational reason this works is the conditional estimate $Pr [A_{i} ∣ ⋂_{j \in S} \overline{A_{j}}] \leq x_{i}$ , which says that avoiding other bad events never inflates a given one beyond its private budget $x_{i}$ . This is exactly the move that the deletion method of 40.07.02 could only approximate by removing defects after the fact; here the defects are forbidden simultaneously, and the bridge is that the same indicator-per-defect bookkeeping which gave $E [X] = \sum_{i} Pr [A_{i}]$ there is now organised by the dependency graph rather than summed flat. The $k$ -SAT and colouring corollaries appear again in the algorithmic story below, where the Moser-Tardos process does not merely certify existence but constructs the assignment; putting these together, the local lemma is the dependency-graph generalisation of the union bound, and its constructive counterpart is the central insight of the modern theory.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Derive the symmetric local lemma from the general form: assuming $Pr [A_{i}] \leq p$ and degree $\leq d$ , set $x_{i} = 1/ (d + 1)$ and show $e p (d + 1) \leq 1$ implies $Pr [A_{i}] \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j})$ .

Hint

With $x_{i} = 1/ (d + 1)$ , $\prod_{j \in Γ (i)} (1 - x_{j}) \geq (1 - 1/ (d + 1))^{d}$ . Use the inequality $(1 - 1/ (d + 1))^{d} > 1/ e$ .

Answer

Put $x_{i} = 1/ (d + 1)$ for all $i$ . Since $∣Γ (i) ∣ \leq d$ and each $1 - x_{j} = 1 - 1/ (d + 1) = d / (d + 1) \in (0, 1)$ , the product over neighbours satisfies $\prod_{j \in Γ (i)} (1 - x_{j}) \geq (\frac{d}{d + 1})^{d} = (1 - \frac{1}{d + 1})^{d}$ . The sequence $(1 - 1/ (d + 1))^{d}$ increases to $1/ e$ and exceeds $1/ e$ for all $d \geq 1$ (equivalently $(1 + 1/ d)^{d} < e \leq (1 + 1/ d)^{d + 1}$ gives $(d / (d + 1))^{d} = (1 + 1/ d)^{- d} > 1/ e$ ). Hence $x_{i} \prod_{j \in Γ (i)} (1 - x_{j}) \geq \frac{1}{d + 1} \cdot \frac{1}{e} = \frac{1}{e ( d + 1 )}$ . The hypothesis $e p (d + 1) \leq 1$ rearranges to $p \leq \frac{1}{e ( d + 1 )} \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j})$ , and since $Pr [A_{i}] \leq p$ the general-form inequality holds for every $i$ . The general local lemma then gives $Pr [⋂ \overline{A_{i}}] \geq (1 - 1/ (d + 1))^{n} > 0$ . Rubric: full credit for the choice $x_{i} = 1/ (d + 1)$ , the bound $(d / (d + 1))^{d} > 1/ e$ , and the rearrangement to $p \leq 1/ (e (d + 1))$ .

Exercise 4 (medium, symbolic).

Prove the $k$ -SAT corollary: a $k$ -CNF in which each clause shares a variable with at most $2^{k} / e - 1$ others is satisfiable. Identify $p$ , the dependency degree, and the application of the symmetric criterion.

Hint

A random fair-coin assignment violates a fixed $k$ -clause with probability $2^{- k}$ . Two clauses are dependent only if they share a variable. Apply $e p (d + 1) \leq 1$ .

Answer

Assign each variable true/false by an independent fair coin. A clause $C = (ℓ_{1} \lor \dots \lor ℓ_{k})$ is unsatisfied exactly when each literal $ℓ_{t}$ is false, one outcome out of $2^{k}$ equally likely settings of its $k$ variables, so $Pr [A_{C}] = 2^{- k} = p$ . The event $A_{C}$ is determined by the variables of $C$ ; $A_{C}$ is mutually independent of all clause-events whose clauses share no variable with $C$ , so the dependency degree is the number of clauses sharing a variable with $C$ , at most $d := 2^{k} / e - 1$ . Then $e p (d + 1) = e \cdot 2^{- k} \cdot 2^{k} / e = 1 \leq 1$ , so the symmetric local lemma gives $Pr [⋂_{C} \overline{A_{C}}] > 0$ , hence a satisfying assignment exists. Rubric: full credit for $Pr [A_{C}] = 2^{- k}$ , the shared-variable dependency structure, and the verification $e p (d + 1) = 1$ at $d = 2^{k} / e - 1$ .

Exercise 5 (medium, symbolic).

Prove the property-B corollary: a $k$ -uniform hypergraph in which each edge meets at most $2^{k - 1} / e - 1$ others is 2-colourable. Compute the monochromatic-edge probability and apply the criterion.

Hint

A random 2-colouring makes a fixed $k$ -edge monochromatic with probability $2 \cdot 2^{- k} = 2^{1 - k}$ (all red or all blue). Edges are dependent only if they share a vertex.

Answer

Colour each vertex red or blue independently and uniformly. A fixed edge $f$ of size $k$ is monochromatic when all $k$ vertices receive the same colour: probability $2 \cdot 2^{- k} = 2^{1 - k} = p$ (two monochromatic colourings out of $2^{k}$ ). The event $A_{f}$ is determined by the colours of $f$ 's vertices, hence mutually independent of all edge-events for edges disjoint from $f$ ; the dependency degree is the number of edges meeting $f$ , at most $d := 2^{k - 1} / e - 1$ . Then $e p (d + 1) = e \cdot 2^{1 - k} \cdot 2^{k - 1} / e = 2^{1 - k} \cdot 2^{k - 1} = 1 \leq 1$ , so the symmetric local lemma yields $Pr [⋂_{f} \overline{A_{f}}] > 0$ : a 2-colouring with no monochromatic edge exists, i.e. the hypergraph has property B. This improves the first-moment bound, which needed the total edge count below $2^{k - 1}$ . Rubric: full credit for $Pr [A_{f}] = 2^{1 - k}$ , the shared-vertex dependency, and the verification $e p (d + 1) = 1$ .

Exercise 6 (medium, symbolic).

(Latin transversals.) Let $M$ be an $n \times n$ matrix in which each symbol appears at most $Δ \leq (n - 1) / (4 e)$ times. Use the local lemma to show $M$ has a Latin transversal: a permutation $σ$ such that the entries $M_{i, σ (i)}$ are all distinct. Set up the bad events and their dependency degree.

Hint

Pick $σ$ a uniformly random permutation. For each pair of cells $(i, σ (i))$ , $(i^{'}, σ (i^{'}))$ carrying the same symbol, let the bad event be that both are chosen. Bound $Pr [A] = 1/ (n (n - 1))$ and the number of dependent events, then apply the symmetric criterion (use the lopsided dependency to get the degree $\leq 4Δ n$ style bound).

Answer

Choose $σ$ uniformly among the $n!$ permutations. The bad events are indexed by ordered pairs of cells ${(i, j), (i^{'}, j^{'})}$ with $i \neq = i^{'}$ , $j \neq = j^{'}$ , and $M_{i, j} = M_{i^{'}, j^{'}}$ ; let $A_{(i, j), (i^{'}, j^{'})}$ be the event $σ (i) = j$ and $σ (i^{'}) = j^{'}$ . Then $Pr [A] = \frac{( n - 2 )!}{n !} = \frac{1}{n ( n - 1 )}$ . A bad event $A$ shares the permutation only through its four coordinates, and the standard count (using that each cell lies in a row and column, each symbol repeats $\leq Δ$ times) bounds the number of bad events dependent with $A$ by $d \leq 4 n Δ$ up to lower-order terms. The symmetric criterion needs $e p (d + 1) \leq 1$ , i.e. $e \cdot \frac{1}{n ( n - 1 )} \cdot (4 n Δ + 1) \leq 1$ , which holds once $Δ \leq (n - 1) / (4 e)$ for large $n$ . Hence a conflict-free $σ$ exists — a Latin transversal. (The sharper constant uses the lopsided local lemma, since conditioning on avoiding some conflicts only decreases the probability of another, the negative-dependence the lopsided form exploits.) Rubric: full credit for $Pr [A] = 1/ (n (n - 1))$ , the dependency-degree bound $O (n Δ)$ , and the application of the symmetric criterion at $Δ = O (n)$ .

Exercise 7 (hard, symbolic).

Prove the asymmetric local lemma's conditional estimate carefully in the two-event base case and explain where mutual independence (versus mere pairwise independence) is used. State precisely the independence hypothesis that the dependency graph encodes.

Hint

In the inductive step, the numerator bound $Pr [A_{i} \cap (\dots) ∣ ⋂_{k \in S_{2}} \overline{A_{k}}] \leq Pr [A_{i} ∣ ⋂_{k \in S_{2}} \overline{A_{k}}] = Pr [A_{i}]$ uses that $A_{i}$ is independent of the whole event $⋂_{k \in S_{2}} \overline{A_{k}}$ , an intersection — not just of each $A_{k}$ separately.

Answer

The dependency graph hypothesis is: for each $i$ , $A_{i}$ is independent of the $σ$ -algebra generated by ${A_{j} : j \in / Γ (i) \cup {i}}$ — equivalently, for every Boolean combination $B$ of non-neighbour events, $Pr [A_{i} \cap B] = Pr [A_{i}] Pr [B]$ . This is strictly stronger than pairwise independence $Pr [A_{i} \cap A_{k}] = Pr [A_{i}] Pr [A_{k}]$ . In the inductive step the conditioning set $S_{2}$ lies entirely outside $Γ (i)$ , so $B := ⋂_{k \in S_{2}} \overline{A_{k}}$ is a combination of non-neighbour events; mutual independence gives $Pr [A_{i} ∣ B] = Pr [A_{i}]$ exactly, which is the step that fails under pairwise independence alone (where $A_{i}$ could correlate with the intersection even if uncorrelated with each $A_{k}$ ). Concretely with two events $A_{1}, A_{2}$ that are dependent ( $Γ (1) = {2}$ ): the base case $S = \emptyset$ gives $Pr [A_{1}] \leq x_{1} (1 - x_{2}) \leq x_{1}$ , and the chain rule yields $Pr [\overline{A_{1}} \cap \overline{A_{2}}] = Pr [\overline{A_{1}}] Pr [\overline{A_{2}} ∣ \overline{A_{1}}] \geq (1 - x_{1}) (1 - x_{2})$ using $Pr [A_{2} ∣ \overline{A_{1}}] \leq x_{2}$ from the $∣ S ∣ = 1$ case. The mutual-independence requirement is invisible here because both events are neighbours; it becomes essential only when $S_{2}$ is nonempty, i.e. when one drops independent events from the conditioning. Rubric: full credit for stating mutual independence as independence from the generated $σ$ -algebra, locating its use at the numerator bound $Pr [A_{i} ∣ ⋂_{S_{2}} \overline{A_{k}}] = Pr [A_{i}]$ , and contrasting with pairwise independence.

Exercise 8 (hard, short-answer).

Explain in one paragraph why the Moser-Tardos resampling algorithm makes the local lemma constructive, and why the existence-only proof of Erdős-Lovász does not by itself yield an efficient algorithm.

Hint

The classical proof bounds a probability $\prod (1 - x_{i})$ that is exponentially small, so naive sampling would take exponentially long to hit a good configuration. Moser-Tardos instead bounds the expected number of local repairs.

Answer

The Erdős-Lovász proof certifies $Pr [⋂_{i} \overline{A_{i}}] \geq \prod_{i} (1 - x_{i}) > 0$ , but that lower bound is typically exponentially small, so drawing fresh random assignments until all bad events vanish takes exponentially many tries — the existence proof gives no efficient search. The Moser-Tardos algorithm replaces global resampling with local repair: start from one random assignment of the underlying independent variables, and while any bad event $A_{i}$ currently holds, resample exactly the variables that $A_{i}$ depends on, repeating until none holds. The key theorem is that, under the same asymmetric condition $Pr [A_{i}] \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j})$ , the expected total number of resamplings is at most $\sum_{i} x_{i} / (1 - x_{i})$ , a polynomial quantity in the relevant parameters — so the algorithm terminates fast and outputs a configuration avoiding every $A_{i}$ . The reason the local process succeeds where global sampling fails is that each repair only disturbs the variables of one event, so progress is not undone wholesale; the analysis (witness trees / entropy compression) shows the random bits consumed by a long run could be losslessly compressed, which is impossible beyond a point, forcing termination. Rubric: full credit for contrasting the exponentially small survival probability with the polynomial resampling bound $\sum_{i} x_{i} / (1 - x_{i})$ , describing the local resample loop, and naming the witness-tree / entropy-compression mechanism.

Advanced results Master

The existence lemma is the floor; its algorithmic, optimal, and lopsided refinements are the structure built on it. The Moser-Tardos algorithm makes the lemma constructive under the identical hypothesis, Shearer's bound identifies the exact boundary of avoidability for a fixed dependency graph, and the lopsided form trades independence for one-sided negative dependence.

Theorem 1 (Moser-Tardos algorithmic local lemma; 2010). Suppose each event $A_{i}$ is determined by a subset $vbl (A_{i})$ of independent random variables $P$ , with the dependency graph given by shared variables, and the asymmetric condition $Pr [A_{i}] \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j})$ holds. The sequential resampling process — repeatedly pick any currently-violated $A_{i}$ and resample all of $vbl (A_{i})$ — resamples event $A_{i}$ an expected number of times at most $x_{i} / (1 - x_{i})$ , so the expected total number of resampling steps is at most $\sum_{i} x_{i} / (1 - x_{i})$ , and the process terminates almost surely with an assignment avoiding all $A_{i}$ ^{[Moser-Tardos 2010]}. In the symmetric regime $x_{i} = 1/ (d + 1)$ this is $O (n / d)$ expected resamplings per event in the relevant scaling, a polynomial-time constructive local lemma.

Theorem 2 (witness-tree encoding). Each resampling of $A_{i}$ during a run is assigned a witness tree $τ$ : a rooted tree labelled by events, recording the causal history of resamplings that forced this one, in which a child's event shares a variable with (or equals) its parent's event, and siblings carry distinct events. Two key facts drive the analysis. First, distinct resamplings of the same event produce distinct witness trees, so the number of resamplings is bounded by the number of proper witness trees that occur. Second, a fixed witness tree $τ$ occurs in the execution with probability at most $\prod_{v \in τ} Pr [A_{[v]}]$ , because the random choices that the tree certifies are independent and each must realise its event. Summing $\prod_{v} Pr [A_{[v]}]$ over all witness trees rooted at $A_{i}$ — a sum controlled by a Galton-Watson branching process with offspring weights $x_{j}$ — gives the bound $x_{i} / (1 - x_{i})$ of Theorem 1 ^{[Moser-Tardos 2010]}.

Theorem 3 (entropy compression, Moser's earlier argument). The witness-tree bound has an information-theoretic shadow: a run of $T$ resamplings consumes $T \cdot (bits per resample)$ uniformly random bits, yet the entire run can be reconstructed from the final state plus an encoding of the witness forest whose length is $T \cdot (bits) - Ω (T)$ when the local-lemma slack is strict. A run longer than a threshold would compress a random string below its entropy, which is impossible; hence the run is short with overwhelming probability. This entropy-compression method (Moser, STOC 2009) preceded the clean witness-tree probability bound and seeded a family of direct combinatorial arguments ^{[Moser-Tardos 2010]}.

Theorem 4 (Shearer's optimal bound; 1985). For a fixed dependency graph $D$ , the set of probability vectors $(Pr [A_{i}])_{i}$ for which every compatible family of events can be avoided is described exactly by the independence polynomial of $D$ : avoidance is guaranteed iff for all induced subgraphs the alternating independent-set sums stay positive. For the $d$ -regular dependency graph the optimal threshold is $p \leq \frac{( d - 1 ) ^{d - 1}}{d ^{d}}$ , asymptotic to $\frac{1}{e d}$ as $d \to \infty$ — improving the symmetric criterion's $\frac{1}{e ( d + 1 )}$ by the missing additive unit and provably best possible: above Shearer's boundary there exist events meeting the probability constraints that cannot all be avoided ^{[Shearer 1985]}. Shearer's condition is the local lemma's tight form; the Erdős-Lovász criterion is a convenient sufficient relaxation.

Theorem 5 (lopsided / lopsidependency local lemma). The mutual-independence hypothesis can be weakened to one-sided negative dependence: $D$ is a lopsidependency graph if $Pr [A_{i} ∣ ⋂_{j \in S} \overline{A_{j}}] \leq Pr [A_{i}]$ for every $i$ and every $S \subseteq {1, \dots, n} ∖ (Γ (i) \cup {i})$ . Under $Pr [A_{i}] \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j})$ the same conclusion $Pr [⋂ \overline{A_{i}}] \geq \prod (1 - x_{i})$ holds. This covers random-permutation models — Latin transversals, the Erdős-Spencer pattern-avoidance bounds — where conditioning on avoiding some conflicts only helps avoid others, and the events are not independent but are negatively associated ^{[Alon-Spencer Ch. 5]}.

Synthesis. Putting these together, the local lemma is a single inequality read four ways: the existence form of Erdős-Lovász, the constructive form of Moser-Tardos, the optimal form of Shearer, and the negatively-dependent lopsided form, and the foundational reason all four cohere is the conditional bound $Pr [A_{i} ∣ avoid a set of others] \leq x_{i}$ — once that holds, the chain rule delivers a positive survival probability, a branching-process sum delivers a polynomial resampling count, and the independence polynomial delivers the exact boundary. This is exactly the generalisation of the deletion method of 40.07.02 that the bridge there pointed to: where deletion tolerates a few defects and removes them, the local lemma forbids all defects at once by exploiting that they are locally sparse, and the Moser-Tardos process is the algorithmic deletion — it resamples defects out of existence. The central insight is that bounded dependence is as good as independence for existence, and the entropy-compression argument shows it is as good for computation: a long failing run would compress randomness past its entropy. This is dual to the second-moment method of 40.07.03, which controls the variance of a single global count, whereas the local lemma controls the interaction structure of many local events; both convert local information into a global existence verdict, and the modern theory of algorithmic sampling and approximate counting grows from Shearer's exact boundary.

Full proof set Master

Proposition 1 (general local lemma, conditional estimate). Under the hypotheses $Pr [A_{i}] \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j})$ with $x_{i} \in [0, 1)$ , for every $i$ and every $S \subseteq {1, \dots, n} ∖ {i}$ , $Pr [A_{i} ∣ ⋂_{j \in S} \overline{A_{j}}] \leq x_{i}$ .

Proof. Induct on $∣ S ∣$ . If $S = \emptyset$ , $Pr [A_{i}] \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j}) \leq x_{i}$ . Otherwise partition $S = S_{1} ⊔ S_{2}$ with $S_{1} = S \cap Γ (i)$ , $S_{2} = S ∖ Γ (i)$ ; assume the conditioning event has positive probability (else there is nothing to bound). Then $$ \Pr\Big[A_i ,\Big|, \bigcap_{j\in S}\overline{A_j}\Big] = \frac{\Pr[A_i \cap \bigcap_{j\in S_1}\overline{A_j}\mid \bigcap_{k\in S_2}\overline{A_k}]}{\Pr[\bigcap_{j\in S_1}\overline{A_j}\mid \bigcap_{k\in S_2}\overline{A_k}]}. $$ For the numerator, $A_{i} \cap ⋂_{j \in S_{1}} \overline{A_{j}} \subseteq A_{i}$ , and since $S_{2} \cap Γ (i) = \emptyset$ the event $A_{i}$ is independent of $⋂_{k \in S_{2}} \overline{A_{k}}$ , so the numerator is $\leq Pr [A_{i} ∣ ⋂_{k \in S_{2}} \overline{A_{k}}] = Pr [A_{i}] \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j})$ . For the denominator, write $S_{1} = {j_{1}, \dots, j_{r}}$ and apply the chain rule; each factor $Pr [\overline{A_{j_{ℓ}}} ∣ ⋂_{m < ℓ} \overline{A_{j_{m}}} \cap ⋂_{k \in S_{2}} \overline{A_{k}}]$ has conditioning set of size $< ∣ S ∣$ , so the induction hypothesis gives $Pr [A_{j_{ℓ}} ∣ \dots] \leq x_{j_{ℓ}}$ and the factor is $\geq 1 - x_{j_{ℓ}}$ . Thus the denominator is $\geq \prod_{ℓ = 1}^{r} (1 - x_{j_{ℓ}}) \geq \prod_{j \in Γ (i)} (1 - x_{j})$ , since $S_{1} \subseteq Γ (i)$ and the extra factors lie in $(0, 1]$ . Dividing, $Pr [A_{i} ∣ ⋂_{j \in S} \overline{A_{j}}] \leq x_{i}$ . $□$

Proposition 2 (positive survival probability). Under the same hypotheses, $Pr [⋂_{i = 1}^{n} \overline{A_{i}}] \geq \prod_{i = 1}^{n} (1 - x_{i}) > 0$ .

Proof. By the chain rule, $Pr [⋂_{i = 1}^{n} \overline{A_{i}}] = \prod_{i = 1}^{n} Pr [\overline{A_{i}} ∣ ⋂_{m < i} \overline{A_{m}}]$ . Each factor equals $1 - Pr [A_{i} ∣ ⋂_{m < i} \overline{A_{m}}] \geq 1 - x_{i}$ by Proposition 1 applied to $S = {1, \dots, i - 1} ∖ {i}$ . Hence the product is $\geq \prod_{i} (1 - x_{i})$ , which is positive since each $x_{i} < 1$ . $□$

Proposition 3 (symmetric criterion). If $Pr [A_{i}] \leq p$ for all $i$ , the dependency graph has maximum degree $\leq d$ , and $e p (d + 1) \leq 1$ , then $Pr [⋂_{i} \overline{A_{i}}] > 0$ .

Proof. Set $x_{i} = 1/ (d + 1)$ . For $d \geq 1$ , $(1 - \frac{1}{d + 1})^{d} = (\frac{d}{d + 1})^{d} = (1 + \frac{1}{d})^{- d} > e^{- 1}$ , since $(1 + 1/ d)^{d} < e$ . Therefore $x_{i} \prod_{j \in Γ (i)} (1 - x_{j}) \geq \frac{1}{d + 1} (\frac{d}{d + 1})^{d} > \frac{1}{e ( d + 1 )} \geq p \geq Pr [A_{i}]$ , the middle inequality from $e p (d + 1) \leq 1$ . The general local lemma (Propositions 1-2) applies and gives $Pr [⋂_{i} \overline{A_{i}}] \geq (1 - 1/ (d + 1))^{n} > 0$ . $□$

Proposition 4 ( $k$ -SAT satisfiability). A $k$ -CNF formula in which every clause shares a variable with at most $2^{k} / e - 1$ other clauses is satisfiable.

Proof. Take an independent uniform assignment of the variables. For each clause $C$ , $A_{C} = {C unsatisfied}$ has $Pr [A_{C}] = 2^{- k}$ , the single falsifying assignment of $C$ 's $k$ variables. The dependency graph joins clauses sharing a variable, of maximum degree $d \leq 2^{k} / e - 1$ . Then $e p (d + 1) \leq e \cdot 2^{- k} \cdot 2^{k} / e = 1$ , so Proposition 3 gives $Pr [⋂_{C} \overline{A_{C}}] > 0$ ; an assignment satisfying every clause exists. $□$

Proposition 5 (Moser-Tardos termination). In the variable model with $Pr [A_{i}] \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j})$ , the resampling process resamples $A_{i}$ an expected $\leq x_{i} / (1 - x_{i})$ times; the expected total number of resamplings is $\leq \sum_{i} x_{i} / (1 - x_{i})$ , finite, so the process halts almost surely at an assignment avoiding all $A_{i}$ .

Proof sketch (witness trees). Order the resamplings as they occur and attach to the $t$ -th resampling (of some event $A_{i}$ ) a rooted witness tree $τ_{t}$ : the root is labelled $A_{i}$ , and reading the resampling log backwards, each earlier resampling of an event $A_{j}$ sharing a variable with a node already in the tree is attached as a child of the deepest such node; siblings receive distinct labels. Distinct resamplings of $A_{i}$ yield distinct witness trees (the log reconstructs uniquely), so the number of times $A_{i}$ is resampled is at most the number of proper witness trees rooted at $A_{i}$ that occur. A fixed tree $τ$ occurs only if, for each node $v$ , the independent fresh variables drawn when $v$ was resampled realised $A_{[v]}$ ; these draws are independent across nodes, so $Pr [τ occurs] \leq \prod_{v \in τ} Pr [A_{[v]}]$ . Summing over all witness trees rooted at $A_{i}$ , $$ \mathbb{E}[#\text{resamplings of }A_i] \le \sum_{\tau\text{ rooted at }A_i}\prod_{v\in\tau}\Pr[A_{[v]}] \le \sum_{\tau}\prod_{v\in\tau}x_{[v]}!!\prod_{j\in\Gamma([v])}!!(1 - x_j). $$ The right side is the total weight of a Galton-Watson branching process in which a node labelled $A_{j}$ has, for each $k \in Γ (j) \cup {j}$ , an independent child labelled $A_{k}$ with "probability" $x_{k}$ ; the expected size of this process rooted at $A_{i}$ is exactly $x_{i} / (1 - x_{i})$ (the standard generating-function identity for the sub-critical branching weights, valid since the $x_{k}$ satisfy the local-lemma inequality). Summing over $i$ gives $E [total resamplings] \leq \sum_{i} x_{i} / (1 - x_{i}) < \infty$ . A process with finite expected length halts almost surely, and when it halts no $A_{i}$ is violated. $□$

Proposition 6 (lopsided local lemma). If $D$ is a lopsidependency graph — $Pr [A_{i} ∣ ⋂_{j \in S} \overline{A_{j}}] \leq Pr [A_{i}]$ for all $i$ and $S \subseteq {1, \dots, n} ∖ (Γ (i) \cup {i})$ — and $Pr [A_{i}] \leq x_{i} \prod_{j \in Γ (i)} (1 - x_{j})$ , then $Pr [⋂_{i} \overline{A_{i}}] \geq \prod_{i} (1 - x_{i}) > 0$ .

Proof. Repeat the induction of Proposition 1. The only place mutual independence was used is the numerator bound $Pr [A_{i} ∣ ⋂_{k \in S_{2}} \overline{A_{k}}] = Pr [A_{i}]$ with $S_{2} \cap Γ (i) = \emptyset$ . Under the lopsidependency hypothesis this equality is replaced by the inequality $Pr [A_{i} ∣ ⋂_{k \in S_{2}} \overline{A_{k}}] \leq Pr [A_{i}]$ , which is all the argument requires, since the numerator is bounded above. Every other step — the chain-rule lower bound on the denominator and the final telescoping — is unchanged, giving $Pr [A_{i} ∣ ⋂_{j \in S} \overline{A_{j}}] \leq x_{i}$ and hence $Pr [⋂_{i} \overline{A_{i}}] \geq \prod_{i} (1 - x_{i})$ . $□$

Connections Master

The deletion method of 40.07.02 is the local lemma's predecessor on the same problems: deletion removes the rare defects from a random object after the fact, while the local lemma forbids them simultaneously by exploiting that each defect is mutually independent of all but a bounded number of others. The Ramsey and hypergraph-2-colouring applications recur in both, but the local-lemma constant is sharper — property B needs only the local edge-meeting degree below $2^{k - 1} / e$ , not the total edge count below $2^{k - 1}$ — because bounded dependence replaces the global first-moment budget with a local one.
The second-moment method of 40.07.03 is the dual tool: where the second moment controls the variance of one global count to force a single structure to appear, the local lemma controls the dependency structure of many local events to force them all to be avoided. Both convert local data — pairwise edge-sharing of subgraph copies there, the dependency neighbourhood here — into a global existence verdict, and the random-graph colouring thresholds of that unit are exactly where local-lemma list-colouring bounds (bounded-degree graphs are $(Δ + 1)$ -list-colourable, sharpened toward $Δ/ ln Δ$ for triangle-free graphs by the local lemma) become the sharpest known.
The entropy / compression analysis of the Moser-Tardos algorithm is the algorithmic face of the entropy method developed in the co-produced 40.07.06: there entropy bounds the number of configurations of a constrained random structure, here the impossibility of compressing a random bit-string below its entropy bounds the length of a resampling run. The witness-tree counting and the Shannon-entropy lower bound are two encodings of the same information-theoretic obstruction, and the local lemma's constructive form is where the probabilistic method becomes an efficient algorithm rather than a pure existence proof.

Historical & philosophical context Master

The Lovász Local Lemma was introduced by Paul Erdős and László Lovász in their 1975 paper on $3$ -chromatic hypergraphs ^{[Erdős-Lovász 1975]}, where the symmetric criterion $e p (d + 1) \leq 1$ first appeared as the tool that proved property B for hypergraphs far denser than the first moment could handle. The lemma answered a recurring difficulty: many natural existence questions place the expected number of bad events well above one, yet the bad events are locally sparse, and no prior method exploited that sparsity. The asymmetric weighted form and the conditional-probability induction are due to the same paper, refined by Spencer; the dependency-graph language became standard through Spencer's 1994 lectures ^{[Spencer 1994]}.

For three decades the lemma was non-constructive: the survival probability $\prod (1 - x_{i})$ is exponentially small, so it certified existence without an efficient search. Partial algorithmic versions (Beck 1991, Alon, Molloy-Reed, Srinivasan) progressively reduced the slack required. The decisive resolution is Robin Moser and Gábor Tardos's 2010 paper ^{[Moser-Tardos 2010]}, which showed the naive "resample a violated event" process terminates in expected $\sum_{i} x_{i} / (1 - x_{i})$ steps under the unmodified asymmetric condition; Moser's 2009 entropy-compression argument for the symmetric $k$ -SAT case preceded it and is the conceptual seed. James Shearer's 1985 paper ^{[Shearer 1985]} had earlier determined the exact boundary of avoidability for a fixed dependency graph through its independence polynomial, giving the optimal $d$ -regular threshold $(d - 1)^{d - 1} / d^{d} \sim 1/ (e d)$ against which the Erdős-Lovász criterion is a clean but lossy sufficient condition.

Bibliography Master

@incollection{erdoslovasz1975,
  author    = {Erd{\H{o}}s, Paul and Lov{\'a}sz, L{\'a}szl{\'o}},
  title     = {Problems and results on 3-chromatic hypergraphs and some related questions},
  booktitle = {Infinite and Finite Sets},
  editor    = {Hajnal, A. and Rado, R. and S{\'o}s, V. T.},
  series    = {Colloquia Mathematica Societatis J{\'a}nos Bolyai},
  volume    = {10},
  publisher = {North-Holland},
  pages     = {609--627},
  year      = {1975}
}

@article{mosertardos2010,
  author  = {Moser, Robin A. and Tardos, G{\'a}bor},
  title   = {A constructive proof of the general Lov{\'a}sz Local Lemma},
  journal = {Journal of the ACM},
  volume  = {57},
  number  = {2},
  pages   = {Art. 11},
  year    = {2010}
}

@article{shearer1985,
  author  = {Shearer, James B.},
  title   = {On a problem of Spencer},
  journal = {Combinatorica},
  volume  = {5},
  number  = {3},
  pages   = {241--245},
  year    = {1985}
}

@inproceedings{moser2009,
  author    = {Moser, Robin A.},
  title     = {A constructive proof of the Lov{\'a}sz Local Lemma},
  booktitle = {Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC)},
  pages     = {343--350},
  year      = {2009}
}

@book{molloyreed2002,
  author    = {Molloy, Michael and Reed, Bruce},
  title     = {Graph Colouring and the Probabilistic Method},
  publisher = {Springer},
  year      = {2002}
}

@book{spencer1994ten,
  author    = {Spencer, Joel H.},
  title     = {Ten Lectures on the Probabilistic Method},
  series    = {CBMS-NSF Regional Conference Series in Applied Mathematics},
  volume    = {64},
  publisher = {SIAM},
  year      = {1994}
}

@book{alonspencer2016,
  author    = {Alon, Noga and Spencer, Joel H.},
  title     = {The Probabilistic Method},
  edition   = {4},
  publisher = {Wiley-Interscience},
  year      = {2016}
}

Prerequisites

40.07.02

Tier anchors

beginner: Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 5 (the local lemma, the symmetric form $ep(d+1) \le 1$, the $k$-SAT and colouring applications); a 'mostly independent bad events' analogy framed for a first-time reader, with the resample-the-conflict picture of the Moser-Tardos process
intermediate: Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 5 §5.1-5.5 (the general/asymmetric local lemma with the $x_i$ weights, the dependency graph, the symmetric corollary, hypergraph 2-colouring, Latin transversals); Molloy-Reed 2002 *Graph Colouring and the Probabilistic Method* (Springer) Ch. 4
master: Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 5 and §5.6-5.7 (the Moser-Tardos algorithmic local lemma, the lopsided version); Erdős-Lovász 1975 *Colloq. Math. Soc. János Bolyai* 10 (Infinite and Finite Sets) (the original lemma); Moser-Tardos 2010 *J. ACM* 57 (the constructive proof via witness trees / entropy compression); Shearer 1985 *Combinatorica* 5 (the optimal lattice-gas / independence-polynomial bound)

References

Alon, N. & Spencer, J. H. — The Probabilistic Method · Wiley, 4th edition (2016). Chapter 5 develops the Lovász Local Lemma: the general (asymmetric) form — if each event $A_i$ has a dependency graph in which it is mutually independent of all but its neighbours, and there exist reals $x_i \in [0,1)$ with $\Pr[A_i] \le x_i \prod_{(i,j) \in E}(1 - x_j)$, then $\Pr[\bigcap \overline{A_i}] \ge \prod (1 - x_i) > 0$ — and the symmetric corollary: if each event has probability $\le p$ and depends on at most $d$ others, then $e\,p\,(d+1) \le 1$ implies $\Pr[\bigcap \overline{A_i}] > 0$. Applications: $k$-SAT (a $k$-CNF in which every clause shares a variable with at most $2^k/e - 1$ others is satisfiable), hypergraph 2-colouring / property B (an $k$-uniform hypergraph with each edge meeting at most $2^{k-1}/e - 1$ others is 2-colourable), Latin transversals, and the Moser-Tardos constructive algorithm with the witness-tree / entropy-compression analysis, plus the lopsided local lemma and a statement of Shearer's optimal bound.
Erdős, P. & Lovász, L. — Problems and results on 3-chromatic hypergraphs and some related questions · In *Infinite and Finite Sets* (A. Hajnal, R. Rado, V. T. Sós, eds.), Colloquia Mathematica Societatis János Bolyai 10, North-Holland (1975), 609-627. The original statement and proof of the Lovász Local Lemma, introduced to show that certain hypergraph colouring and Ramsey-type configurations exist despite the first moment being far too large; the symmetric criterion $ep(d+1) \le 1$ and the application to property B.
Moser, R. A. & Tardos, G. — A constructive proof of the general Lovász Local Lemma · *Journal of the ACM* 57 (2010), no. 2, Art. 11. The resample-a-violated-event random process: starting from an independent random assignment of the underlying variables, while some event $A_i$ holds, pick one and resample exactly the variables it depends on. Under the asymmetric Lovász condition the process terminates after an expected $\sum_i x_i/(1 - x_i)$ resamplings; the proof reconstructs each resampling by a *witness tree* whose probability of occurring is the product of the event probabilities, and a counting/coupling argument (the entropy-compression idea of Moser's earlier STOC 2009 proof) bounds the expected number of trees.
Shearer, J. B. — On a problem of Spencer · *Combinatorica* 5 (1985), 241-245. The optimal version of the local lemma for a given dependency graph: the events can be avoided for all probability vectors below a boundary determined by the independent-set (independence) polynomial of the dependency graph; for the $d$-regular case the optimal bound is $p \le (d-1)^{d-1}/d^d$, asymptotically $1/(ed)$, sharper than the symmetric $ep(d+1) \le 1$ by the absence of the extra factor and tight.
Spencer, J. H. — Ten Lectures on the Probabilistic Method · CBMS-NSF Regional Conference Series in Applied Mathematics 64, SIAM (1994). Lecture 8 on the Lovász Local Lemma, the dependency-graph formulation, and the worked $k$-SAT, colouring, and Latin-transversal applications.

Estimated time

beginner: 18m
intermediate: 47m
master: 88m