Browse › Combinatorics › 175 Talagrand’s expectation thresholds, discrete convexity, and graph decompositions
Integral and fractional expectation thresholds are equivalent
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 Talagrand's conjecture that integral and fractional expectation thresholds are within a universal constant factor, with the same covering budget.
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
- Xuan Fang and Tianyu Wang, A Log-Star Comparison Between Expectation Threshold and Fractional Expectation Threshold (arXiv:2609.30680, v1 25 Sep 2026, v2 8 Oct 2026). Proves a log-star comparison between q and q_f; the v2 abstract states that an OpenAI result "proving the equivalence of fractional and integral thresholds" supersedes the note, which is kept for historical reference.
Comments and discussion
- Gil Kalai, Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans (blog post, 2026-10-07). Links this paper as a "companion result" making integral and fractional expectation thresholds equivalent up to a universal constant, and notes that the release's proofs "will need to be checked and digested by the mathematical community."
Formalization
- OpenAI, Family 175 Lean scope note (
lean/docs/175.md) (OpenAI Math Release, Oct 2026). States that the formalization proves $q_f(\mathcal F)\le25\cdot512^4 q(\mathcal F)$ for nonempty proper increasing families on finite nonempty ground sets, with budget $1/2$ for both covers and fractional weights allowed on the empty set, and links the comparator statementTalagrandExpectationThreshold.lean. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Chong Shangguan, Thresholds and spread in set systems of bounded VC-dimension (arXiv:2609.30263, 24 Sep 2026). Its abstract claims to verify "Talagrand's integral--fractional conjecture for families of any fixed VC dimension", a special case of Theorem 1.1 that is not among the earlier comparisons the introduction surveys.
- Michel Talagrand, The Status of my favorite problems (author's website, 2026). Section 3 states Conjecture 3.9 (every weakly p-small set is (αp)-small), Talagrand's own recent formulation of the comparison proved in Theorem 1.1, and records Park's log log bound as the best known result.
Digests and expositions
- Gradient Damage, Every OpenAI Math Result, Part 2 of 4: PCP for PPAD, Birkhoff Conjecture and 82 More (video, 14 Oct 2026). Chapter 24 summarizes result family 175, including the universal-factor comparison of integral and fractional expectation thresholds. [family-level]
- Open Mathematics Courses, Thresholds and expectation thresholds (undated). This eight-lesson course includes expositions of the three manuscripts, with proofs, examples and exercises, and identifies its author and self-checker as Claude Opus 5.5 with independent review incomplete. [AI-generated per source] [family-level]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 175
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026,
author = {{OpenAI}},
title = {{Integral and fractional expectation thresholds are equivalent}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026/paper.pdf}{OAI:Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/175.md. The Lean statements have not been checked by people against the paper's claims.
Family 175: Talagrand’s expectation thresholds, discrete convexity, and graph decompositions
Proves that integral and fractional expectation thresholds differ by at most a universal factor, and resolves Talagrand's discrete-convexity conjecture. An application proves the Ascoli–He–Park–Talagrand graph-decomposition conjecture: every graph's edges split into a universally bounded number of fixed pieces, each with containment threshold at most a universal constant times the original graph's integral expectation threshold. The pieces' embeddings need not agree on shared vertices.
Other papers in this family:
- Graph Decompositions at the Integral Expectation Threshold · October 5, 2026
- Talagrand’s discrete-convexity conjecture · September 23, 2026