The second Kahn–Kalai conjecture with an edge-count bound

Proves the second Kahn–Kalai conjecture: for every finite simple graph H with h ≥ 1 edges and at most n vertices, its appearance threshold in G(n,p) is at most C p_{\mathrm E}(n,H)(1+\log_2 h), with universal C. Here p_{\mathrm E} is the least density at which every subgraph of H has expected copy count at least 1/2. (Lean)

Manuscript

The second Kahn–Kalai conjecture

September 24, 2026 · source · Lean formalization available · cite as \cite{OAI:The-second-Kahn-Kalai-conjecture-September-24-2026}

We prove the second Kahn–Kalai conjecture. For every finite simple graph H with h ≥ 1 edges and at most n vertices, the threshold for G(n,p) to contain an ordinary copy of H is at most C p_{\mathrm E}(n,H)(1+\log_2 h), where C is universal. Here p_{\mathrm E}(n,H) is the least density at which every subgraph of H has expected copy count at least one half.

Result 176 · Combinatorics. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.