Episode 175, October 2026

Talagrand, up to a constant?

Preprints claim that fractional and ordinary expectation thresholds agree up to a fixed factor, prove Talagrand’s discrete convexity conjecture, and split every graph into boundedly many pieces that each appear near its expectation threshold

Covers result 175 in OpenAI’s catalog: all 3 papers. See its connections to other results and the work it cites.

Play Episode 175: Talagrand, up to a constant? A graph on nine dots whose edges are split into three pieces, coloured yellow, teal and pink (our drawing).

7:13. English captions available. The video loads from YouTube when you press play.

Chapters

The claim, in plain words

Keep each element of a finite set with probability p, and consider a property that stays true when elements are added. A cover is a list of small sets such that every set with the property contains one of them; its cost is the sum of p^|S|, and a cover of cost at most one half shows by a union bound that the property has probability at most one half. The expectation threshold q is the largest p with such a cover. Talagrand also allowed fractional covers, with weights between zero and one and every member covered by total weight at least one; the fractional threshold q_f is never smaller than q. For example, on four points, the sets containing abc, abd or acd have q ≈ 0.565 (cover abc and ad) and q_f = 1/√3 ≈ 0.577 (weight one half on ab, ac and ad), our example. As the papers recount, Kahn and Kalai conjectured in 2007 that the true threshold is at most q times a logarithmic factor; Frankston, Kahn, Narayanan and Park proved the fractional version and Park and Pham the conjecture itself. Talagrand conjectured in 2010 that q and q_f agree up to a fixed factor; special kinds of weights were handled one by one, and in September 2026 Park reached a factor growing like log log(1/q).

Result 175 is three OpenAI preprints. Integral and fractional expectation thresholds are equivalent (12 pages, September 23, 2026), Theorem 1.1: “For every finite nonempty X and every nonempty proper increasing family F ⊆ 2^X, q_f(F) ≤ 25·512⁴ q(F). Both thresholds use the budget 1/2.” Talagrand’s discrete-convexity conjecture (10 pages, same date), Theorem 1.1: with k = 2⁷⁵, for every N, every p in (0,1) and every family D of subsets of [N], if μ_p(D) ≥ 1 − 1/k then the sets inside no union of k members of D form a p-small family; “no monotonicity is assumed.” Graph Decompositions at the Integral Expectation Threshold (11 pages, October 5, 2026) uses the second, as “an essential companion input”, to prove Conjecture 8.1 of Ascoli, He, Park and Talagrand: for absolute k and L, the edges of every graph H on at most n vertices split into k pieces with p_c(H_i;n) ≤ L q(H;n). “The pieces may be empty and may share vertices. The partition depends only on H, n and is fixed before the random host is sampled.”

What it doesn’t claim

No small constants. The first theorem’s 25·512⁴ is about 1.7 × 10¹², so, since q_f never exceeds 1, it says something only when q is below about 6 × 10⁻¹³. The third allows about 7.6 × 10³¹ pieces and gives no value for L; by our reading of its cutoffs (5.2), its bound is trivial for random graphs on fewer than about 5.3 × 10¹⁵ vertices. It does not say the whole graph appears at L q(H;n): each piece is tested on its own, and “their embeddings need not agree on shared vertices.” In our simulation of a random graph on 2,000 vertices with edge probability 3/n, 68 to 125 vertices were isolated, so there was no perfect matching, yet every sample had a matching of more than 900 edges. And discrete convexity needs a very likely family: for D = {∅} on N ≥ 2 points with μ_p(D) = 1/2, every nonempty set is exceptional for every k, and the cheapest cover costs Np, which tends to ln 2 > 1/2 (our example).

Where it stands

Posted as preprints: OpenAI, three preprints of 12, 10 and 11 pages, dated September 23 and October 5, 2026
Peer reviewed: Not yet
Checked in Lean: The first two theorems, formalized by OpenAI; not the graph decomposition; not run by us

Last checked October 19, 2026. None of the preprints has been revised since it was added to the repository in its initial commit on October 6, 2026. OpenAI published a Lean formalization whose comparator statements match the first two theorems with their exact constants (expectation thresholds, discrete convexity). By our count the proofs take 47 files and 4,834 lines and 36 files and 4,259 lines, excluding Mathlib (thresholds, discrete convexity), with no unproved steps by our search; we have not rebuilt them. The graph-decomposition paper is not formalized, nor are the corollaries about unions of two members, which also use a September 2026 preprint by Chen Li. The papers are not among those OSVerify reviewed, and we have seen no expert review.

How the proofs go

Rounding a fractional cover. Suppose a fractional cover costs at most one half at density r, but no ordinary cover is cheap at r/C. Spread each set’s weight evenly over its points, and colour every point at random in levels whose chances grow by a factor of 256. The multiscale selector estimate gives, with probability at least 9/10, one member that keeps most of its weight at every level at once (“Separate estimates at individual scales could choose different members”). Weighting each point by 512 to the power four minus its colour, the expected total must be at least 9/40, but independence caps it at 1/10. The estimate adapts methods of Park and Pham, of Pham, and of Bednorz, Martynek and Meller.
Discrete convexity at half measure. If a family has probability at least one half at density q, the sets inside no union of 32 members are cheap to cover at q/2⁷⁰: an exceptional set forces the identity Σ_U⊆S (−1)^|U| b(U)³² = 0 among biased Fourier coefficients, which leaves enough weight on its subsets to build a cover with an elementary covering lemma.
An exact coupling. 2⁷⁰ random rows, each exactly at density p, have a union exactly at density 2⁷⁰p (when that is below one; otherwise the union covers everything). All rows lie in the family with probability at least 31/32, so the first step applies with 32 × 2⁷⁰ = 2⁷⁵ unions, back at density p.
Splitting a graph. Graphs of degeneracy below 1000 split into forests, star forests and small pieces, embedded one star at a time. For denser graphs, a class of typical random graphs at twice the expectation threshold has probability at least 1 − 2⁻⁷⁵; discrete convexity puts a copy of H inside a union of 2⁷⁵ of them, and each edge goes to one. High-degree vertices are separated out, and the edges to them are embedded by Hall’s theorem after a compression lemma keeps the number of tests small.

The numbers in the video

Our exact computation of q and q_f for every nonempty proper increasing property on up to 5 points: on 5 points, 200 of the 208 types have ratio exactly 1 and the largest ratio is 1.052579; the four-point example above has ratio 1.021501.
Our perfect-matching simulation (2,000 vertices, edge probability 3/n, 20 samples) and our example D = {∅}.
The constants: 25·512⁴ = 1,717,986,918,400; 2⁷⁵; the third paper’s k ≈ 7.57 × 10³¹; its explicit cutoffs (5.2) hold only from about 5.33 × 10¹⁵ (our computation).
The Lean count: our count of the import closures.

Read the source

Integral and fractional expectation thresholds are equivalent (PDF), 12 pages.
Talagrand’s discrete-convexity conjecture (PDF), 10 pages.
Graph Decompositions at the Integral Expectation Threshold (PDF), 11 pages.
The Lean scope note.
The collection’s catalog, where this is result 175.

The 3 papers in this result

OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.

Graph Decompositions at the Integral Expectation Threshold main paper
Integral and fractional expectation thresholds are equivalent companion
Talagrand’s discrete-convexity conjecture companion

Transcript

Read the full script

0:00The question

Pick each item of a finite set independently with probability p, and ask about a property that stays true when you add items, like a random graph containing a triangle. One way to show the property is unlikely is a cover: a list of small sets such that every set with the property contains one of them. A set of size s shows up with chance p^s, so if those chances add up to at most one half, the property has chance at most one half. The expectation threshold q is the largest p with such a cheap cover. Talagrand also allowed fractional covers: weights between zero and one, with every member covered by total weight at least one. That gives the fractional threshold, q_f, which is never smaller. On four points a, b, c, d, take the sets containing abc, abd or acd. One best ordinary cover, abc and ad, works up to p of about 0.565. Half weights on the pairs ab, ac and ad work up to 1/√3, about 0.577. Kahn and Kalai conjectured in 2007 that the true threshold, where the property has probability one half, is at most q times a logarithmic factor. Frankston, Kahn, Narayanan and Park proved the fractional version, and Park and Pham proved the conjecture itself. Talagrand had conjectured, in 2010, that the two expectation thresholds always agree up to a fixed factor. Earlier work handled special kinds of weights, and in September 2026, Park reached a factor that grows like log log of one over q. In our check of every such property on up to 5 points, the ratio is never more than about 1.05, and it is exactly one for 200 of the 208 types. Small cases say nothing about the worst case.

1:52The claims

Result 175 is three OpenAI preprints. The first, 12 pages long, dated September 23, 2026, proves Talagrand’s comparison: q_f is at most 25 × 512⁴, about 1.7 trillion, times q, for every nonempty proper increasing property, with the same budget of one half. The second, 10 pages, same date, proves Talagrand’s discrete convexity conjecture: with k equal to 2⁷⁵, if a family of sets has probability at least 1 − 1/k, then the sets that lie inside no union of k of its members have a cheap cover at the same p. The third, 11 pages, dated October 5, uses the second to prove a conjecture of Ascoli, He, Park and Talagrand: the edges of every graph split into a bounded number of pieces, each of which appears in the random graph with probability one half once p reaches a fixed multiple of the whole graph’s expectation threshold. Not claimed: small constants. Since q_f never exceeds one, the first theorem only says something when q is below about 6 × 10⁻¹³. The third allows about 8 × 10³¹ pieces and gives no value for its multiple, and by our reading its written proof only bites when the random graph has more than 5 quadrillion vertices. Nor does it say the whole graph appears at that density: each piece is tested on its own, and their copies need not fit together. A perfect matching shows why. In our simulation of a random graph on 2,000 dots, with 3/n as the edge probability, about 100 dots are isolated, so there is no perfect matching, yet a matching of more than 900 edges is there, so any tenth of a perfect matching appears. And discrete convexity needs a very likely family: in our example, a family of probability one half fails for every number of unions.

3:57How the proofs go

The first proof argues by contradiction. Suppose the property has a fractional cover of cost at most one half at a density r, but no cheap ordinary cover at r over the constant. Spread each set’s fractional weight evenly over its points. Then colour every point at random at several scales, with chances growing by a factor of 256. The key estimate says that, with probability at least 9/10, one single member keeps most of its weight at every scale at once; separate estimates at each scale could pick different members. Weighting each point by 512 to the power (4 − its colour), the expected total must then be at least 9/40, but independence caps it at 1/10. The estimate adapts methods of Park and Pham, of Pham, and of Bednorz, Martynek and Meller. The second proof first works at probability one half and a lower density: if a family has probability at least one half at density q, the sets inside no union of 32 members have a cheap cover at q/2⁷⁰. An exceptional set forces an identity among the family’s biased Fourier coefficients, raised to the 32nd power, and that leaves enough weight on its subsets to build a cover. Then an exact coupling returns to density p: 2⁷⁰ random rows, each distributed exactly at density p, whose union, when 2⁷⁰ p is below one, is distributed exactly at that density. By a union bound, all the rows lie in the family with probability at least 31/32, so the first step applies, with 32 × 2⁷⁰ unions, which is 2⁷⁵. The third proof splits by degeneracy, a measure of how dense its densest part is. Sparse graphs break into forests, then star forests, then small pieces that embed one star at a time. For dense ones, it builds a class of typical random graphs at twice the expectation threshold, with probability at least 1 − 2⁻⁷⁵, and discrete convexity puts a copy of the graph inside a union of 2⁷⁵ typical graphs; each edge goes to one of them. High-degree vertices are separated out, and the edges between them and the rest are embedded with Hall’s theorem, after a compression lemma keeps the number of tests small.

6:17Where it stands

All three are preprints, not peer reviewed, and not revised. OpenAI’s Lean files state and prove the first two theorems with their exact constants, in about 4,800 and 4,300 lines, with no gaps we could find by search; we did not run the check. Not formalized: the graph-decomposition paper, and the papers’ corollaries about unions of two members, which also rely on a September 2026 preprint by Chen Li. None of the papers is among those OSVerify reviewed, and we have seen no expert review. If they hold, Talagrand’s fractional and ordinary expectation thresholds agree up to a fixed factor, his discrete convexity conjecture is true, and every graph splits into a bounded number of pieces that each appear at a fixed multiple of the whole graph’s expectation threshold.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.