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.
released 2026-09-24 | 2 theorems · 3 lemmas · 5 proofs · 4,822 words |
PLAY LEVEL 1 »(pdf)
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.