You have 500 bad events, each with probability 1/50, and each sharing randomness with at most 4 other events. Does the Lovász Local Lemma guarantee that all bad events can simultaneously be avoided?
ANo — with 500 events each at probability 1/50, the expected number of bad events is 10, so some must occur
BYes — the LLL condition ep(d+1) ≤ 1 becomes e·(1/50)·5 ≈ 0.272 ≤ 1, so P(none occur) > 0
CNo — the LLL only applies when bad events are fully independent, not merely locally dependent
DYes — with probability 1/50 per event, each event is unlikely enough to guarantee avoidability regardless of dependency structure
Check the LLL condition: p = 1/50, d = 4, so ep(d+1) = e · (1/50) · 5 = e/10 ≈ 0.272 ≤ 1. The condition is satisfied, so P(no bad event occurs) > 0. Option A is the classic confusion: a positive expected number of bad events does not prevent the possibility of avoiding all of them. The union bound fails to prove the result, but the LLL's exploitation of limited dependency succeeds. The LLL is precisely the tool for situations where naive expectation arguments are misleading.
Question 2 Multiple Choice
In the LLL's condition ep(d+1) ≤ 1, what does 'd' represent?
AThe total number of bad events in the combinatorial problem
BThe maximum number of bad events that share randomness with a given bad event — its degree in the dependency graph
CThe probability that any particular bad event occurs
DThe number of independent random choices underlying the probability space
d is the maximum degree in the dependency graph — the largest number of other bad events that any single bad event can share randomness with. Two bad events are neighbors in the dependency graph if knowing whether one occurred gives information about the other (i.e., they are not independent). A common error is to set d to the total number of events; the LLL is powerful precisely because d only counts local neighbors, not all other events. When d is small relative to 1/p, the LLL condition is easily satisfied even with large numbers of events.
Question 3 True / False
The LLL is more powerful than a simple union bound because it can guarantee P(no bad event) > 0 even when the union bound ΣP(Aᵢ) exceeds 1.
TTrue
FFalse
Answer: True
The union bound P(∪Aᵢ) ≤ ΣP(Aᵢ) becomes vacuous when the sum exceeds 1, since all probabilities are at most 1. In problems with many bad events — even individually unlikely ones — the sum easily exceeds 1, and the union bound cannot prove that any avoidance is possible. The LLL exploits limited dependency structure to prove positivity of P(no bad event) in exactly these situations. This is why the LLL is so important in combinatorics: it handles regimes where the naive probabilistic argument completely breaks down.
Question 4 True / False
The LLL condition ep(d+1) ≤ 1 is both necessary and sufficient: if this condition fails, it is very difficult to simultaneously avoid most bad events.
TTrue
FFalse
Answer: False
The condition ep(d+1) ≤ 1 is sufficient but not necessary. It is a clean, checkable threshold that guarantees P(no bad event) > 0, but the actual threshold at which simultaneous avoidance becomes impossible can be considerably weaker — the LLL is not tight at this bound. In some structured settings, stronger variants (such as the asymmetric LLL) give tighter conditions. The Common Misconceptions section of this topic makes this point explicitly: failing the ep(d+1) ≤ 1 condition does not prove impossibility.
Question 5 Short Answer
Why can't a simple union bound prove the existence results that the LLL proves, and what key property does the LLL exploit instead?
Think about your answer, then reveal below.
Model answer: A union bound says P(∪Aᵢ) ≤ ΣP(Aᵢ). When there are many bad events, this sum easily exceeds 1, making the bound vacuous — it cannot establish that P(no bad event) > 0. The union bound also implicitly treats all events as if they were independent, ignoring the dependency structure entirely. The LLL exploits a weaker, more realistic property: limited dependency. Each bad event needs to share randomness with at most d other events, and if ep(d+1) ≤ 1, then an inductive argument shows that the probability each event occurs, conditioned on all nearby events being avoided, remains at most p. This mutual consistency is maintained across the whole system simultaneously, proving that global avoidance is achievable. The insight is that you don't need full independence — bounded locality in the dependency graph is enough.
The LLL's power is that it converts 'there are too many bad interactions for a naive argument' into 'the interactions are local enough that we can avoid them all.' This has made it one of the most widely applied tools in probabilistic combinatorics, with applications ranging from graph coloring to hypergraph satisfiability to Ramsey theory.