VibeMathedMath problems solved with AI
Sign in

The second Kahn-Kalai conjecture

For a graph HH with at least one edge and at most nn vertices, let pc(n,H)p_c(n,H) be the density at which G(n,p)G(n,p) contains a copy of HH with probability 1/21/2, and pE(n,H)p_E(n,H) the least density at which every subgraph F⊆HF\subseteq H has expected copy count at least one (or one half). Always pE≤pcp_E\le p_c, and perfect matchings and Hamilton cycles show a logarithmic gap can occur. Kahn and Kalai conjectured in 2007 that this elementary first-moment obstruction determines the threshold up to a logarithm, uniformly in HH. The abstract (first) Kahn-Kalai conjecture was proved by Park and Pham; it does not give the graph statement, and the best prior general bound was O(log⁡2)O(\log^2) loss. Is pc(n,H)=O(pE(n,H)log⁡n)p_c(n,H)=O(p_E(n,H)\log n) for every such HH, with a universal constant?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Random graphs; thresholds and expectation thresholds
Posed by
Jeff Kahn and Gil Kalai (Thresholds and expectation thresholds, Combin. Probab. Comput. 16, 2007)
Year posed
2007
Years open
19y
Solved
2026-09-24
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
36 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Claims Theorem 1.1: for every n≥2n\ge2 and every finite simple graph HH with h≥1h\ge1 edges and at most nn vertices, pc(n,H)≤min⁡{1,2048e50pE(n,H)(1+log⁡2h)}p_c(n,H)\le\min\{1,2048e^{50}p_E(n,H)(1+\log_2 h)\}, hence pc(n,H)≤6144e50pE(n,H)log⁡2np_c(n,H)\le6144e^{50}p_E(n,H)\log_2 n. The logarithm depends only on the number of edges of HH, which is stronger than the conjectured log⁡n\log n. The proof builds on Tran's spread-link cores and the Mossel-Niles-Weed-Sun-Zadik resampling, with a tree reduction replacing Tran's proposed coupling conjecture. Constants are explicit but huge; it says nothing about optimal constants or about hypergraph targets.

What the AI did

Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems. The release README says the vast majority of results used one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result; this result is not among the README's stated exceptions (the Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscript is authored as OpenAI with no human author named.

Verification

No independent mathematician has checked this yet. Checked here: abstract, introduction and Theorem 1.1, read against the Kahn-Kalai formulation as cited; the paper notes that normalising expected counts at one half instead of one changes pEp_E by at most a factor two, so the conjecture is unchanged. The proof was not refereed. Lean-checked: the release's formalization catalogue lists ComparatorChallenges/SecondKahnKalai.json with declaration OAI.LeanBlast.SecondKahnKalai.secondKahnKalaiBounds. The statement was read here: for n >= 2 and any finite simple graph H with at least one edge and at most n vertices, the actual containment threshold (infimum over p of probability >= 1/2) is at most min(1, 2048 e^50 p_E (1 + log2 e(H))) and at most 6144 e^50 p_E log2 n, with p_E defined over all subgraphs of H. That is the headline claim. Not rebuilt here.

Sources

Changelog1 change

Discussion