TheoremStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 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 asymmetric Lovász Local Lemma for finitely many events

Statement

Let $D$ be a dependency digraph for finite events $(A_{i})_{i \in I}$ . If there are reals $0 \leq x_{i} < 1$ such that $P (A_{i}) \leq x_{i} \prod_{j \in N_{D}^{+} (i)} (1 - x_{j})$ for every $i$ , then $P ⁣ (⋂_{i \in I} A_{i}^{c}) \geq \prod_{i \in I} (1 - x_{i}) > 0.$

Facts & Assumptions

Given: Events, a dependency digraph, and parameters satisfying the Statement.

[L1]

Under these hypotheses, conditioning $A_{i}$ on any positive-probability intersection of other event complements gives probability at most $x_{i}$ (The conditional-probability induction underlying the Lovász Local Lemma).

[L2]

The finite chain rule factors the probability of an intersection through successive positive conditional probabilities (The multiplication rule and finite chain rule for conditional probability).

[L3]

Multiplication by a positive real preserves inequalities (Sign rules for products and monotonicity of multiplication).

Proof

technique · induction

1.1

For an empty event family, the intersection is the whole space and both empty products equal $1$ .

base

1.2

Order a nonempty family as $i_{1}, \dots, i_{m}$ and assume the first $r - 1$ complements have intersection probability at least $\prod_{q < r} (1 - x_{i_{q}}) > 0$ .

ihchoose

2.1

By [L1], the conditional probability of $A_{i_{r}}$ given those complements is at most $x_{i_{r}}$ , so the conditional probability of $A_{i_{r}}^{c}$ is at least $1 - x_{i_{r}} > 0$ .

step 1.2L1

3.1

Multiplying by the positive prefix probability gives $P (⋂_{q \leq r} A_{i_{q}}^{c}) \geq \prod_{q \leq r} (1 - x_{i_{q}}) > 0$ .

step 1.2step 2.1L2L3algebra

4.1

Induction through $r = m$ proves both the lower bound and positivity.

step 1.1step 3.1discharge-induction∎

Depends on

Used by

The symmetric Lovász Local Lemma under ep(d+1)≤1 Corollary

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 12 results over 4 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, Theorem 5.1.1 (standard reference, not scraped)
Y. Zhao, MIT 18.218 Probabilistic Method in Combinatorics, Theorem 5.1 (standard reference, not scraped)