Motivation
A first-moment argument controls the sum of bad-event probabilities. It may fail when there are many events even though each event interacts with only a few others. Local dependence offers another route to proving that all bad events can be avoided simultaneously.
The proof needs more than pairwise independence. Conditioning on several individually unrelated events can reveal information not visible in any single pair. A dependency graph therefore encodes independence from an entire collection of nonneighbors, and a conditional-probability induction is what makes that collection manageable.
This note proves the finite local lemma in its general form and in a convenient symmetric specialization, with complete coloring and clause applications. It is an existence theorem; a fast constructive resampling algorithm would require an additional result, not an inference from positive probability alone.
Definitions
Definition 2.3.1
(Bad events and a dependency graph)
Let be events in a finite probability space. A dependency graph is a simple graph on their indices such that each event is independent of the -algebra generated by all events whose indices are neither nor neighbors of .
Thus, for any joint condition built from those nonneighbor events and their complements, has its original probability whenever that condition has positive probability. Pairwise independence from each event separately is weaker and is not the definition used here. Write for the neighbor set.
For a set of indices, avoidance means the event , with probability one for the empty set. Conditional probabilities are used only after their conditioning events have been proved to have positive probability.
A useful construction starts with independent base variables. If event depends only on a set of those variables, join two event indices whenever their variable sets overlap. The nonneighbor events jointly depend on variables outside 's set; independence of the base-variable groups gives exactly the required -algebra independence.
A finite -uniform hypergraph is a family of -element vertex subsets. A proper two-coloring here means no hyperedge is monochromatic. For a -CNF application, every clause uses distinct variables with one literal per variable and has no tautological opposite pair.
Theorem/Proposition
Theorem 2.3.2
(Asymmetric finite local lemma)
Suppose numbers satisfy
for every . Then
More generally, for every index and set not containing ,
All conditioning events in this assertion have positive probability as part of the theorem.
Corollary 2.3.3
(A symmetric local dependence criterion)
If the dependency graph has maximum degree at most , every bad event has probability at most , and
then simultaneous avoidance has positive probability. Here is the usual exponential constant. For , the sufficient condition is simply , and joint independence gives the product of the individual avoidance probabilities.
Corollary 2.3.4
(Sparse overlap guarantees colorings and satisfying assignments)
A -uniform hypergraph with , in which each edge intersects at most other edges, has a nonmonochromatic two-coloring whenever . If every vertex belongs to at most edges, it suffices to use .
A -CNF formula in which every variable occurs in at most clauses is satisfiable whenever
Zero-overlap cases use the preceding independent-event convention. These are sufficient conditions, not characterizations of all colorable hypergraphs or satisfiable formulas.
Proof sketch or proof idea
Inductively bound conditional bad probabilities before multiplying them
Proof
(Conditional avoidance bounds by induction on the conditioning set)
We prove the conditional bound by induction on the size of , together with positivity of all avoidance conditions. At , the assumed probability inequality is at most , because each product factor is at most one.
Suppose conditional bounds have been proved for conditioning sets smaller than . Avoidance of every set of size at most has positive probability: list its indices in any order and factor its avoidance probability by the chain rule. Each successive factor is at least for the corresponding index, using a conditioning set of size at most . Their product is positive.
Now take and split it into and . The second set contains only nonneighbors. If the first is empty, dependency independence gives the original probability, already at most .
Otherwise, conditioning first on avoidance of gives
The numerator is by the dependency hypothesis. Factor the denominator by ordering . Each conditional avoidance factor has a conditioning set consisting of and an earlier proper part of , whose size is at most . Induction therefore bounds it below by the corresponding .
Consequently
This proves the next conditional level. The same chain-rule argument then gives positivity of avoidance sets of size . Induction reaches every finite set, so no conditioning on a zero-probability event has slipped into the calculation.
Finally order all events and factor the complete avoidance probability. Its factors are at least the respective , giving the theorem's positive product lower bound. With no events, the empty product is one, consistent with the same conclusion.
Proof X-ray
The induction controls the denominator created by neighboring conditions
The key move is to prove more than is asked: a conditional bound for every conditioning set, not just the final product. The product bound alone is not inductive, whereas the conditional bounds feed the chain rule directly.
Each hypothesis then has one job. The dependency graph is used only in the numerator, and it must be the joint, -algebra form, because avoidance of is a joint condition on many nonneighbors. The induction hypothesis is used only in the denominator, at conditioning sets of size at most , and it is there that neighbor avoidance could have lowered the probability. The factors for neighbors outside are discarded in the last inequality; that slack is why the hypothesis carries the full neighbor product. Positivity is proved at each level before any division at the next, which is what makes the logical order sound.
Choose one uniform parameter for bounded degree
Proof
(The symmetric criterion from one uniform parameter)
For choose every . A vertex with at most neighbors has
The strict final comparison is , which follows from , obtained by integrating over . Thus the stated non-strict upper bound on suffices. The asymmetric lemma applies and gives positive avoidance probability.
For , each event is independent of all other events jointly. Factoring the avoidance probability gives exactly , positive if each probability is below one.
The formula would give at , outside the lemma's parameter range; that is why this boundary is stated separately.
Independent base choices verify the required graph, not merely pairwise counts
Proof
(Colorings and satisfying assignments)
Color every hypergraph vertex independently and uniformly in two colors. The event that one -edge is monochromatic has probability . Its base variables are its vertex colors. Disjoint hyperedges use disjoint base-variable sets, and all nonneighbor events together still use only colors outside that edge. The intersection graph is therefore a valid dependency graph.
If each vertex belongs to at most hyperedges, each of an edge's vertices can connect it to at most others. Counting repeats only overestimates, so is valid. Apply the symmetric criterion to obtain a coloring avoiding every monochromatic-edge event.
For clauses, assign all Boolean variables independently and fairly. A clause with distinct variables is false on exactly one of their assignments, giving probability . Join clauses sharing variables. The same group-independence argument verifies a dependency graph, with degree at most . Avoiding every false-clause event is exactly a satisfying assignment, proving the second application.
Opposite literal signs across clauses do not invalidate this graph: dependence is determined by shared base variables, not whether the literal texts are identical. Distinct-variable and nontautology conditions ensure the displayed clause probability; simplifying other clauses requires recomputing their parameters.
Existence and efficient construction remain different questions
The lemma's positive lower bound can be extremely small. Even independent fair-bit bad events have avoidance probability when each event is its bit being zero. An avoiding assignment exists, but independent full resampling until success has expected trials.
Thus the existence theorem alone does not prove a polynomial expected runtime for finding the object. A local resampling theorem could exploit more structure, but it needs its own algorithm, invariant and termination analysis. The present applications prove that solutions exist, with no unstated efficient search guarantee.
Worked examples
Worked example 2.3.5
(Ten-uniform sparse incidence works for arbitrarily many edges)
Suppose each vertex of a ten-uniform hypergraph lies in at most ten edges. The dependency degree is at most , and each bad event has probability .
Using gives . A proper two-coloring exists regardless of the total number of edges. The elementary first-moment sum would instead require the edge count to be less than , showing why local dependence can help beyond that global test.
Worked example 2.3.6
(Bounded variable occurrences guarantee an eight-CNF model)
Take clauses with eight distinct variables each, and let each variable occur in at most ten clauses. Each failure probability is and the dependency degree is at most .
The sufficient expression is . Therefore the formula is satisfiable, with no bound on its total clause count needed here. If the numerical test failed, the theorem would be silent rather than prove unsatisfiability.
Worked example 2.3.7
(An asymmetric certificate can be checked with exact fractions)
Use three independent finite choices with event probabilities , , . A path on their three indices is a valid dependency graph; adding unnecessary dependency edges is allowed. Choose every .
The endpoint allowance is , exceeding . The middle allowance is , exceeding . Thus avoidance has probability at least . The actual independent avoidance probability is , illustrating that a valid certificate need not be sharp.
Concept lensCombinatorial
A dependence bound replaces the total number of bad events by local interactions
The graph does not claim events are mutually independent. It isolates where conditioning can matter, and the parameters pay for that local effect. Independent variable groups justify the graph; the conditional induction then supplies the global simultaneous-avoidance conclusion.
Common mistakes
Counterexample mode
Pairwise independence does not justify an empty dependency graph
Let be independent fair bits. Set , and . Each event has probability one half, and every pair has joint probability one quarter.
Yet avoiding and forces , which makes true, so simultaneous avoidance has probability zero. An empty dependency graph would be invalid: is not independent of the joint condition formed from and . Pairwise probability checks cannot replace the -algebra hypothesis.
The two remaining errors concern the lemma's parameters and the reach of its conclusion.
Common mistake
(Substituting at degree zero)
The proof divides by products of , so it needs . At the uniform choice equals one and the lemma does not apply. The case is handled directly: joint independence gives avoidance probability , positive when every .
Common mistake
(Reading a sufficient test as a characterization or an algorithm)
A sufficient numerical test has no converse: if the theorem is silent, and the instance may still be colorable or satisfiable. Success proves existence rather than a fast algorithm, since the guaranteed probability may be as small as .
Summary
A dependency graph supplies joint nonneighbor independence. Conditional avoidance induction proves the asymmetric local lemma and its positive product bound, then one uniform gives a bounded-degree criterion. Sparse-overlap coloring and SAT follow from independent base variables, with probability, representation and algorithmic limits explicit.
Exercises
Quick check
(A twelve-uniform hypergraph has each vertex in at most twenty edges. Verify two-colorability using the degree bound and .)
Its monochromatic-event probability is .
Solution · Answer
The degree is at most . The criterion is , which is below . Thus an avoiding two-coloring exists. The statement does not bound the total number of hyperedges or supply a polynomial search algorithm.
Quick check
(Check the sufficient criterion for six-CNF with each variable in at most four clauses. Explain why failure of such a test for another formula would not certify unsatisfiability.)
Use the shared-variable dependency graph.
Solution · Answer
The degree bound is and bad-event probability is . Hence , proving satisfiability. A failed criterion only means this sufficient theorem does not establish a model; satisfiable instances can have many dependent clauses or redundant repetitions.
Quick check
(For the two-bit counterexample, list the four outcomes and which bad events occur. Verify pairwise independence and zero simultaneous avoidance.)
At the outcome all three events occur.
Solution
At , events all occur. At only occurs; at only occurs; at only occurs. Each event occupies two of four outcomes, and each pair intersects only at , with probability one quarter, the product of their marginal probabilities.
Every outcome has a bad event, so avoidance is impossible. The empty graph fails the required joint-independence condition despite passing every pairwise check, exactly the distinction used in the proof.