LemmaStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-13

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The conditional-probability induction underlying the Lovász Local Lemma

Statement

Let $D$ be a dependency digraph for finite events $(A_{i})_{i \in I}$ . Suppose $0 \leq x_{i} < 1$ and $P (A_{i}) \leq x_{i} \prod_{j \in N_{D}^{+} (i)} (1 - x_{j})$ for every $i$ . If $S \subseteq I ∖ {i}$ and $P (⋂_{j \in S} A_{j}^{c}) > 0$ , then $P ⁣ (A_{i} ∣ ⋂_{j \in S} A_{j}^{c}) \leq x_{i} .$

Facts & Assumptions

Given: Events, a dependency digraph, parameters, an index $i$ , and a set $S$ satisfying the Statement.

[L1]

Conditional probability is formed only for a positive-probability conditioning event (Conditional probability $P (A ∣ B)$ for $P (B) > 0$ ).

[L2]

The finite chain rule factors probabilities of successive intersections when all prefix conditioning events are positive (The multiplication rule and finite chain rule for conditional probability).

[L3]

A dependency digraph makes $A_{i}$ independent of every conjunction of complements indexed by non-out-neighbours (Dependency digraphs for a finite family of bad events).

Proof

technique · induction

1.1

For $S = \emptyset$ , the conditional probability is $P (A_{i}) \leq x_{i} \prod_{j \in N_{D}^{+} (i)} (1 - x_{j}) \leq x_{i}$ .

givenbasealgebra

1.2

Assume the assertion holds whenever the conditioning set has fewer than $m$ elements, and let $∣ S ∣ = m > 0$ . Put $S_{1} = S \cap N_{D}^{+} (i)$ and $S_{2} = S ∖ S_{1}$ .

ihconstruct

2.1

If $S_{1} = \emptyset$ , [L3] gives $P (A_{i} ∣ ⋂_{j \in S} A_{j}^{c}) = P (A_{i}) \leq x_{i}$ .

step 1.2L1L3algebra

2.2

Suppose $S_{1} \neq \emptyset$ , order it as $j_{1}, \dots, j_{r}$ , and write $C_{t} = ⋂_{j \in S_{t}} A_{j}^{c}$ . Since $P (C_{1} \cap C_{2}) > 0$ , also $P (C_{2}) > 0$ . Conditional multiplication gives $P (A_{i} ∣ C_{1} \cap C_{2}) = P (A_{i} \cap C_{1} ∣ C_{2}) / P (C_{1} ∣ C_{2}) \leq P (A_{i} ∣ C_{2}) / P (C_{1} ∣ C_{2}) = P (A_{i}) / P (C_{1} ∣ C_{2})$ , where the equality uses [L3] because $S_{2}$ consists of non-out-neighbours of $i$ .

step 1.2L1L2L3choose

3.1

The chain rule writes $P (C_{1} ∣ C_{2}) = \prod_{q = 1}^{r} (1 - P (A_{j_{q}} ∣ ⋂_{h \in S_{2} \cup {j_{1}, \dots, j_{q - 1}}} A_{h}^{c}))$ . Every displayed conditioning set has fewer than $m$ elements and positive probability, because its complement intersection contains the positive event $C_{1} \cap C_{2}$ . The induction hypothesis therefore bounds the conditional probability by $x_{j_{q}}$ , so this denominator is at least $\prod_{j \in S_{1}} (1 - x_{j})$ .

step 2.2step 1.2L2ihalgebra

4.1

Consequently $P (A_{i} ∣ ⋂_{j \in S} A_{j}^{c}) \leq P (A_{i}) / \prod_{j \in S_{1}} (1 - x_{j}) \leq x_{i} \prod_{j \in N_{D}^{+} (i) ∖ S_{1}} (1 - x_{j}) \leq x_{i}$ .

step 2.2step 3.1givenalgebra

5.1

Steps 2.1 and 4.1 cover the two possibilities for $S_{1}$ , completing the induction. No conditional probability with zero denominator was formed.

step 1.1step 2.1step 4.1L1discharge-induction∎

Depends on

Used by

The asymmetric Lovász Local Lemma for finitely many events Theorem

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 12 results over 5 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

J. Matousek and J. Vondrak, The Probabilistic Method, proof of Theorem 5.1.1 (standard reference, not scraped)
Y. Zhao, MIT 18.218 Probabilistic Method in Combinatorics, proof of Theorem 5.1 (standard reference, not scraped)