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

> Spreading credit fractionally beats whole-set covers by at most a fixed factor in Talagrand's threshold theory.

Canonical: https://closedform.nishachay.tech/e/openai-math-2026-175/
Last updated: 2026-10-14

**Spreading credit fractionally beats whole-set covers by at most a fixed factor in Talagrand's threshold theory.**

**Trust:** Formal proof listed · **Papers:** 3 · **First paper:** September 23, 2026 · **Field:** Combinatorics · **Entry:** 175

*Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error.

Expectation thresholds give cheap lower estimates for when a random set first has a property. Talagrand asked whether allowing fractional covers changes them by more than a fixed factor. One paper proves it does not, and a second proves his discrete-convexity conjecture. A third paper uses these to claim a graph-decomposition conjecture about random graphs.

## At a glance

- **First step:** 2010 (Michel Talagrand, who posed both conjectures)
- **Significance:** Major. It settles two of Talagrand's conjectures on thresholds and applies them to a recent graph conjecture.
- **Trust:** Formal proof listed
- **Field:** Combinatorics (3 papers)

## The explanation

Take ten lights. Each one turns on by itself with chance p, independently. Ask when at least five are on with probability one half. An exact count of the cases gives p of about 0.452. That number is the threshold for the event "at least five on".

There is a cheaper estimate, built from covers. Any five lights that are on form one of 252 possible groups. Each group is fully on with chance p⁵. Add these up: 252p⁵. While that sum is at most one half, the event cannot happen half the time. The sum reaches one half at p of about 0.288. So 0.288 is a safe lower estimate. Such a list of small sets, one inside every outcome of the event, is an integral cover. The best p a cover can certify, with total cost at most one half, is the integral expectation threshold.

Talagrand also allowed fractional covers. Instead of picking whole sets, you spread credit. Each outcome of the event must collect total credit of at least 1 from the sets inside it. Put credit 1/5 on each single light. Any five lights then collect exactly 1. The cost is 10 × 1/5 × p, which is 2p. That works up to p of 0.25, so this particular fractional cover does worse. In general, fractional covers have more freedom. So the fractional threshold is at least the integral one[1].

Michel Talagrand conjectured around 2010 that the extra freedom gains at most a fixed factor[2]. This mattered because of a related result. Park and Pham proved the Kahn–Kalai conjecture with integral covers[3]. Earlier work had compared fractional and integral covers only in special cases. Talagrand handled covers made of single elements[4]. Later work reached a loss of order log log of the number of elements[5]. Park then removed that dependence, but his factor still grew as the threshold got small[6].

One paper proves Talagrand's conjecture, removing both kinds of growth[7]. The fractional threshold is at most 25 × 512⁴ times the integral one. That is about 1.7 trillion. The number is huge, but it is the same for every family of sets, however large[8].

A second paper proves a related conjecture of Talagrand, about discrete convexity[9]. Take a family of sets that a random set lands in very often. Talagrand predicted that unions of a fixed number of its members contain almost everything[10]. The sets left over should have a cheap integral cover. The paper proves this with the fixed number 2⁷⁵, for any family at all[11].

A third paper applies these ideas to random graphs. It claims the graph-decomposition conjecture of Ascoli, He, Park and Talagrand[12]. Any target graph splits into a fixed number of pieces. Each piece appears in a random graph at a density within a fixed factor of the integral threshold[13]. Without splitting, the known bound loses a logarithmic factor[14]. There is a catch. Each piece appears somewhere, but the copies need not fit together on shared points[15]. That proof uses the discrete-convexity theorem as its main input[16]. The hard part was the links between points with many neighbors and points with few[17]. Knowing that a class of graphs is typical was not enough for that step[18].

How sure is this? A computer proof checker called Lean has checked formal versions of the first two results. They cover the comparison with the constant 25 × 512⁴, and discrete convexity with 2⁷⁵. The graph-decomposition paper is not in the Lean scope note, so its result remains a claim. No specialist review of the papers has been published.

**What it doesn't show.** This does not give constants of practical size, and the graph pieces need not fit together on shared points.

## Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

## Hype check

Major if the proofs hold. Lean has checked formal versions of the comparison and discrete-convexity results. The graph decomposition is outside the Lean note, and no specialist review is published.

## Words used

- **Threshold:** The probability p at which a random set has a given property half the time.
- **Integral cover:** A list of small sets such that every outcome of the event contains at least one of them.
- **Fractional cover:** An assignment of credit to small sets so that every outcome of the event collects total credit at least 1.
- **Expectation threshold:** The largest p at which some cover has total cost at most one half.
- **Discrete convexity:** Talagrand's prediction that unions of a few members of a likely family contain almost every set.
- **Lean:** A computer program that checks each step of a formally written proof.

## The original papers (3)

- [Graph Decompositions at the Integral Expectation Threshold](https://github.com/openai/math/blob/main/preprints/Graph-Decompositions-at-the-Integral-Expectation-Threshold-October-5-2026/graph-threshold-decompositions.pdf) - October 5, 2026
- [Integral and fractional expectation thresholds are equivalent](https://github.com/openai/math/blob/main/preprints/Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026/paper.pdf) - September 23, 2026 · Formal proof listed
- [Talagrand’s discrete-convexity conjecture](https://github.com/openai/math/blob/main/preprints/Talagrands-discrete-convexity-conjecture-September-23-2026/paper.pdf) - September 23, 2026 · Formal proof listed

- [Lean notes](https://github.com/openai/math/blob/main/lean/docs/175.md)

## Quoted lines from the paper (18)

[1] From [Integral and fractional expectation thresholds are equivalent](https://github.com/openai/math/blob/main/preprints/Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026/paper.pdf):

> In particular, $q(\F)\le q_f(\F)$, by taking $g$ to be the indicator of an integral cover.

[2] From [Integral and fractional expectation thresholds are equivalent](https://github.com/openai/math/blob/main/preprints/Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026/paper.pdf):

> Their fractional relaxation allows a member to be covered by a total weight of one, distributed among its subsets. Talagrand conjectured that this relaxation changes the expectation threshold by at most a universal factor.

[3] From [Integral and fractional expectation thresholds are equivalent](https://github.com/openai/math/blob/main/preprints/Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026/paper.pdf):

> Park and Pham proved the corresponding bound with $q$ in place of $q_f$, resolving the Kahn--Kalai conjecture.

[4] From [Integral and fractional expectation thresholds are equivalent](https://github.com/openai/math/blob/main/preprints/Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026/paper.pdf):

> Talagrand settled the case of singleton sets; DeMarco and Kahn treated clique-counting certificates, and Frankston, Kahn, and Park treated arbitrary weights on pairs.

[5] From [Integral and fractional expectation thresholds are equivalent](https://github.com/openai/math/blob/main/preprints/Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026/paper.pdf):

> Fischer and Person's sampling argument for sufficiently large sets, combined with Pham's logarithmic rounding bound, gives a loss of order $\log\log(4|X|)$. This consequence is recorded in the expanded version of Pham's paper.

[6] From [Integral and fractional expectation thresholds are equivalent](https://github.com/openai/math/blob/main/preprints/Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026/paper.pdf):

> More recently, Park obtained the dimension-independent bound \[ q_f(\F)\le Kq(\F)\max\{1,\log\log(1/q(\F))\} \] for a universal $K$. The factor here still grows as $q(\F)$ tends to zero.

[7] From [Integral and fractional expectation thresholds are equivalent](https://github.com/openai/math/blob/main/preprints/Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026/paper.pdf):

> The factor here still grows as $q(\F)$ tends to zero. Theorem … removes both kinds of dependence.

[8] From [Integral and fractional expectation thresholds are equivalent](https://github.com/openai/math/blob/main/preprints/Integral-and-fractional-expectation-thresholds-are-equivalent-September-23-2026/paper.pdf):

> The constant is independent of $|X|$, the sizes of the minimal members of $\F$, and the support of the fractional cover.

[9] From [Talagrand’s discrete-convexity conjecture](https://github.com/openai/math/blob/main/preprints/Talagrands-discrete-convexity-conjecture-September-23-2026/paper.pdf):

> Talagrand formulated the discrete-convexity conjecture in: a fixed number of members of a sufficiently likely family should cover every set outside a $p$-small exceptional family.

[10] From [Talagrand’s discrete-convexity conjecture](https://github.com/openai/math/blob/main/preprints/Talagrands-discrete-convexity-conjecture-September-23-2026/paper.pdf):

> Talagrand formulated the discrete-convexity conjecture in: a fixed number of members of a sufficiently likely family should cover every set outside a $p$-small exceptional family.

[11] From [Talagrand’s discrete-convexity conjecture](https://github.com/openai/math/blob/main/preprints/Talagrands-discrete-convexity-conjecture-September-23-2026/paper.pdf):

> The family $\mathcal D$ is arbitrary; no monotonicity is assumed.

[12] From [Graph Decompositions at the Integral Expectation Threshold](https://github.com/openai/math/blob/main/preprints/Graph-Decompositions-at-the-Integral-Expectation-Threshold-October-5-2026/graph-threshold-decompositions.pdf):

> We prove the graph-decomposition conjecture of Ascoli, He, Park, and Talagrand.

[13] From [Graph Decompositions at the Integral Expectation Threshold](https://github.com/openai/math/blob/main/preprints/Graph-Decompositions-at-the-Integral-Expectation-Threshold-October-5-2026/graph-threshold-decompositions.pdf):

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

[14] From [Graph Decompositions at the Integral Expectation Threshold](https://github.com/openai/math/blob/main/preprints/Graph-Decompositions-at-the-Integral-Expectation-Threshold-October-5-2026/graph-threshold-decompositions.pdf):

> Theorem … removes this logarithmic loss after partitioning the target into a bounded number of pieces.

[15] From [Graph Decompositions at the Integral Expectation Threshold](https://github.com/openai/math/blob/main/preprints/Graph-Decompositions-at-the-Integral-Expectation-Threshold-October-5-2026/graph-threshold-decompositions.pdf):

> The assertion concerns each fixed piece's ordinary threshold; their embeddings need not agree on shared vertices.

[16] From [Graph Decompositions at the Integral Expectation Threshold](https://github.com/openai/math/blob/main/preprints/Graph-Decompositions-at-the-Integral-Expectation-Threshold-October-5-2026/graph-threshold-decompositions.pdf):

> We use the same-parameter integral covering theorem from \emph{Talagrand's discrete-convexity conjecture}, which proves the discrete conjecture formulated in.

[17] From [Graph Decompositions at the Integral Expectation Threshold](https://github.com/openai/math/blob/main/preprints/Graph-Decompositions-at-the-Integral-Expectation-Threshold-October-5-2026/graph-threshold-decompositions.pdf):

> Their Section 8 isolates the bipartite edges between high- and low-degree vertices as a principal remaining difficulty.

[18] From [Graph Decompositions at the Integral Expectation Threshold](https://github.com/openai/math/blob/main/preprints/Graph-Decompositions-at-the-Integral-Expectation-Threshold-October-5-2026/graph-threshold-decompositions.pdf):

> Membership in a typical class alone does not ensure this; the class must control unions of arbitrarily many such conditions.

## Other sources

- [M. Talagrand, “Are many small sets explicitly small?”, Proceedings of the 42nd ACM Symposium on Theory of Computing (2010), 13–36](https://doi.org/10.1145/1806689.1806693)
- [J. Park and H. T. Pham, “A proof of the Kahn–Kalai conjecture”, Journal of the American Mathematical Society 37(1) (2024), 235–243, arXiv:2203.17207](https://arxiv.org/abs/2203.17207)
- [J. Kahn and G. Kalai, “Thresholds and expectation thresholds”, Combinatorics, Probability and Computing 16(3) (2007), 495–502, arXiv:math/0603218](https://arxiv.org/abs/math/0603218)
- [openai/math release notes (2026): model provenance and review status](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model”

## Related

- [Bounded-degree coboundary expanders](https://closedform.nishachay.tech/e/openai-math-2026-177/) - Combinatorics
- [The second Kahn–Kalai conjecture with an edge-count bound](https://closedform.nishachay.tech/e/openai-math-2026-176/) - Combinatorics
- [Seymour’s second-neighborhood conjecture](https://closedform.nishachay.tech/e/openai-math-2026-173/) - Combinatorics
- [Classification of finite Euclidean Ramsey configurations](https://closedform.nishachay.tech/e/openai-math-2026-172/) - Combinatorics
- [Deterministic nonbipartite Ramanujan graphs in every fixed degree](https://closedform.nishachay.tech/e/openai-math-2026-178/) - Combinatorics
- [Combinatorics](https://closedform.nishachay.tech/science/mathematics/combinatorics/) - Field · 37 results
- [Graph theory](https://closedform.nishachay.tech/topic/graph-theory/) - Topic · 40 results
- [Open since the 2010s](https://closedform.nishachay.tech/open-since/2010s/) - Era · 31 results
- [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results
- [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20175%5D%20)