Talagrand’s expectation thresholds, discrete convexity, and graph decompositions

3 papersLean

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.

Watch

▶Introduction: the problem and why it mattersin preparation

▶The presented solutionin preparation

Papers 3

Graph Decompositions at the Integral Expectation Threshold

OpenAI · October 5, 2026

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.

Read PDF Download Source

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}
}

$First page of Integral and fractional expectation thresholds are equivalent$

Integral and fractional expectation thresholds are equivalent

OpenAI · September 23, 2026

We prove Talagrand's conjecture that integral and fractional expectation thresholds are within a universal constant factor, with the same covering budget.

Read PDF Download Source

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}
}

Talagrand’s discrete-convexity conjecture

OpenAI · September 23, 2026

We prove Talagrand's discrete-convexity conjecture. There is a universal integer k such that, whenever an arbitrary family has Bernoulli product measure at least $1-1/k$, the sets not contained in a union of k members admit a cover of total cost at most 1/2 at the same density.

Read PDF Download Source

Cite

@misc{OAI:Talagrands-discrete-convexity-conjecture-September-23-2026,
  author = {{OpenAI}},
  title = {{Talagrand's discrete-convexity conjecture}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Talagrands-discrete-convexity-conjecture-September-23-2026/paper.pdf}{OAI:Talagrands-discrete-convexity-conjecture-September-23-2026}},
  year = {2026}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Scope

Talagrand's expectation-threshold conjecture asks whether the fractional and integral expectation thresholds are comparable by an absolute constant. The formalized result proves $q_f(\mathcal F)\le25\cdot512^4 q(\mathcal F)$ for every nonempty proper increasing family on a finite nonempty ground set. Both thresholds use cover budget $1/2$, and fractional covers may assign weights to every subset, including the empty set.

The formalized result proves Talagrand's discrete-convexity assertion with $k=2^{75}$. If a family of subsets of a finite nonempty ground set has Bernoulli-$p$ measure at least $1-1/k$, then the sets not contained in a union of $k$ members form a $p$-small family: they have a containment cover of total $p$-cost at most $1/2$. This holds for every $0<p<1$, with repeated members allowed in the union and no monotonicity assumption.

Comparator links

Result	Comparator statement
Integral–fractional expectation-threshold comparison	TalagrandExpectationThreshold.lean
Talagrand discrete convexity	TalagrandDiscreteConvexity.lean

Scope note on GitHub →