Lovász Local Lemma (Introduction)
A powerful tool for proving the existence of combinatorial objects when the events we want to avoid are only locally dependent.
1. Simple Explanation
- Goal: Show that a set of “bad” events can simultaneously be avoided, even when the events are not completely independent.
- Key idea: If each bad event is rare and its dependency on other events is limited, then the probability that none of the bad events occur is still positive.
- Why it matters: Many combinatorial problems involve events that are mostly independent except for a few “local” overlaps (e.g., edges sharing a vertex in a graph). The Lovász Local Lemma (LLL) turns this intuition into a rigorous inequality.
2. The Classic Symmetric Version
Let
- (A_1, A_2, \dots, A_n) be events in a probability space.
- Each event (A_i) has probability at most (p).
- Each event (A_i) is independent of all but at most (d) of the other events.
Symmetric LLL
If
[
e,p,(d+1) \le 1
]
then
[
\Pr!\left(\bigcap_{i=1}^{n} \overline{A_i}\right) > 0 .
]
Interpretation
The product (p(d+1)) measures how “dangerous” the worst case is: a rare event multiplied by the number of other events it can interact with.
The factor (e) comes from the combinatorial analysis of the lemma.
3. The General (Asymmetric) Version
If each event (A_i) has a probability (p_i) and a dependency graph (G) (vertices are events, edges indicate dependence), then there exist numbers ({x_i}_{i=1}^n) with (0 \le x_i < 1) such that
[ p_i \le x_i \prod_{(i,j)\in E(G)} (1-x_j) ]
implies
[ \Pr!\left(\bigcap_{i=1}^{n} \overline{A_i}\right) ; \ge ; \prod_{i=1}^{n} (1-x_i) ; > ; 0 . ]
Why the asymmetric form?
It allows each event to have a different “size” (probability) and a different local structure (degree in the dependency graph).
4. Key Points to Remember
| Concept | What it means | Why it matters |
|---|---|---|
| Bad events | The outcomes we want to avoid (e.g., “vertex (v) has degree > 2”). | Define the problem in probabilistic terms. |
| Probability (p) | Upper bound on each bad event’s probability. | Controls how “rare” the events are. |
| Dependency degree (d) | Number of other events a given event depends on. | Captures the “locality” of interactions. |
| Dependency graph | Graph where vertices are events, edges indicate dependence. | Visual tool to check the conditions. |
| Condition (e p (d+1) \le 1) | Criterion for the symmetric LLL to hold. | Easy to check for many applications. |
| Conclusion | Positive probability of avoiding all bad events. | Gives an existence proof. |
5. Worked Example: Proper Vertex‑Coloring of a Graph
Problem
Given a simple graph (G=(V,E)) with maximum degree (\Delta), show that (G) has a proper ((\Delta+1))-vertex‑coloring.
Random experiment
Assign each vertex a color uniformly at random from ({1,\dots,\Delta+1}).
Bad events
For each edge (e={u,v}), let
(A_e ={ \text{color}(u)=\text{color}(v)}).
- (\Pr(A_e) = \frac{1}{\Delta+1} =: p).
Dependency
Two events (A_{e_1}) and (A_{e_2}) are dependent iff the edges share a vertex.
Each edge is incident to at most (2\Delta-2) other edges, so
(d \le 2\Delta-2).
Check LLL condition
[ e,p,(d+1) = e \cdot \frac{1}{\Delta+1} \cdot (2\Delta-1) \le e \cdot \frac{2\Delta-1}{\Delta+1} . ]
For (\Delta \ge 2), this is at most (e\cdot 1 < 3).
The LLL requires (\le 1); however, for (\Delta \ge 2) the condition fails.
What to do?
Use the asymmetric LLL with better bounds or a different probability distribution—e.g., choose colors from a larger palette ({1,\dots, k}) with (k > e(\Delta+1)).
Revised experiment
Let (k = \lceil e(\Delta+1) \rceil).
Now (\Pr(A_e)=1/k \le 1/(e(\Delta+1))).
Dependency degree remains (d \le 2\Delta-2).
Check:
[ e,p,(d+1) \le e \cdot \frac{1}{e(\Delta+1)} \cdot (2\Delta-1) = \frac{2\Delta-1}{\Delta+1} < 2 . ]
For (\Delta \ge 3), we get (< 1).
Thus the LLL guarantees a proper coloring using (k) colors.
Conclusion
There exists a proper vertex‑coloring with at most (k = O(\Delta)) colors.
While Brooks’ theorem gives (\Delta+1) colors, the LLL demonstrates an existential proof with a slightly larger palette.
6. Quick Revision Summary
- Lovász Local Lemma: If bad events