Browse › Combinatorics › 176 The second Kahn–Kalai conjecture with an edge-count bound
The second Kahn–Kalai conjecture
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- acprk, R13: Second Kahn–Kalai conjecture: constant 2048e^50 ≈ 10^25 → 10^5 (GitHub repository acprk/openai-math-remarks, undated draft). A remark that re-tunes the parameters of this paper's proof and claims computer-certified constants of about 10^5 and 2·10^5 in place of 2048e^50 and 6144e^50, assuming the manuscript's lemmas. [AI-generated per source]
Formalization
- OpenAI math release, Lean scope notes for family 176: The second Kahn–Kalai conjecture with an edge-count bound (lean/docs/176.md, 2026). The scope note reports formalization of both bounds of Theorem 1.1 using the actual containment and expectation thresholds, with a universal factor times $1+\log_2|E(H)|$ and the consequent $\log_2 n$ bound. [AI-generated per source]
- OpenAI math release, SecondKahnKalai.lean (comparator statement) (lean/ComparatorChallenges). The Lean statement
OAI.LeanBlast.SecondKahnKalai.secondKahnKalaiBoundsof both bounds of Theorem 1.1 with the constants 2048e^50 and 6144e^50; the challenge file leaves the proof assorry, to be supplied separately.
Related prior literature mentioned by others
- Jinyoung Park, Thresholds (Proceedings of the ICM 2026, vol. 6, pp. 199–211, 2026). Park surveys the two Kahn–Kalai conjectures and fractional expectation thresholds; Kalai's October 7 post on the release points readers to his account of this lecture.
Possibly relevant literature (found by the agent, not checked)
- Q. Dubroff, Thresholds vs. expectation thresholds for non-spanning graphs (arXiv:2602.00278, January 2026). Constructs graphs H on m vertices whose threshold exceeds q_f(H) by a factor of order √(log m), bearing on how far the factor (1+log₂ h) in Theorem 1.1 can be reduced for small targets.
- J. Park, A dimension-free comparison between expectation thresholds and fractional expectation thresholds (arXiv:2609.14681, September 2026). A comparison of q and q_f with a log log loss, related to the integral-versus-fractional comparison the introduction cites as context.
- R. Ascoli, X. He, J. Park, M. Talagrand, A reformulation of the discrete Convexity Conjecture via k-thresholds (arXiv:2608.11183, August 2026). Bounds thresholds of graph-containment properties through decompositions into graphs with known thresholds, a parallel graph-specific comparison with expectation thresholds.
Digests and expositions
- Claude Opus 5.5 / Open Mathematics Courses, The second Kahn–Kalai conjecture (October 2026). A lesson reconstructing the graph hierarchy and conditional spread argument leading to the paper's explicit edge-count bound, with preceding lessons on resampling and tree covering. [AI-generated per source]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 176
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:The-second-Kahn-Kalai-conjecture-September-24-2026,
author = {{OpenAI}},
title = {{The second Kahn--Kalai conjecture}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/The-second-Kahn-Kalai-conjecture-September-24-2026/paper.pdf}{OAI:The-second-Kahn-Kalai-conjecture-September-24-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/176.md. The Lean statements have not been checked by people against the paper's claims.
Family 176: 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.
This is the only paper in this family.