Family 176CombinatoricsLeanNot yet digested

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.

Manuscripts in this family · 1

Sep 24, 2026·paper.pdfLean

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.

Full abstract