Browse › Combinatorics › 175 Talagrand’s expectation thresholds, discrete convexity, and graph decompositions
Graph Decompositions at the Integral Expectation Threshold
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 graph-decomposition conjecture of Ascoli, He, Park, and Talagrand. Every graph admits a partition into a universally bounded number of fixed edge pieces, each having ordinary containment threshold at most a universal constant times the original graph's integral expectation threshold. The partition is chosen before sampling the random host, and the separate embeddings of the pieces need not agree on shared vertices.
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.
Formalization
- OpenAI, Family 175 Lean scope note (
lean/docs/175.md) (OpenAI Math Release, Oct 2026). Documents the formalized discrete-convexity theorem with $k=2^{75}$, which this manuscript uses as a companion input; the graph-decomposition theorem (Theorem 1.1) is not listed in its scope. [family-level]
Related prior literature mentioned by others
- Ruben Ascoli, Xiaoyu He, Jinyoung Park and Michel Talagrand, A reformulation of the discrete Convexity Conjecture via $k$-thresholds (arXiv:2608.11183, 2026-08-11). Listed as the problem source; relates discrete convexity to generalized thresholds and graph decompositions and proves comparisons for low-degeneracy graph-containment families. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Jia-Qi Yang, Graph Decompositions at the Expectation Threshold (arXiv:2609.20864, v1 15 Sep 2026, withdrawn in v2 21 Sep 2026). Claimed to remove the maximum-degree hypothesis from a decomposition theorem of Ascoli, He, Park and Talagrand for degeneracy up to C log n / log log n, the same problem as Theorem 1.1; the manuscript was withdrawn citing concerns about its analysis.
- Tuan Tran, Fractional expectation thresholds and the "second" Kahn-Kalai conjecture (arXiv:2609.20546, v2 24 Sep 2026). Bounds the spread of the uniform measure on copies of H in K_n in terms of the graphic expectation threshold, related to the comparison between p_c(H;n) and q(H;n) discussed in the paper's introduction.
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 Ascoli–He–Park–Talagrand graph-decomposition application. [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:Graph-Decompositions-at-the-Integral-Expectation-Threshold-October-5-2026,
author = {{OpenAI}},
title = {{Graph Decompositions at the Integral Expectation Threshold}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Graph-Decompositions-at-the-Integral-Expectation-Threshold-October-5-2026/graph-threshold-decompositions.pdf}{OAI:Graph-Decompositions-at-the-Integral-Expectation-Threshold-October-5-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:
- Integral and fractional expectation thresholds are equivalent · September 23, 2026
- Talagrand’s discrete-convexity conjecture · September 23, 2026