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

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

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

One paper proves Talagrand's conjecture, removing both kinds of growthSource 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 largeSource 8.

A second paper proves a related conjecture of Talagrand, about discrete convexitySource 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 everythingSource 10. The sets left over should have a cheap integral cover. The paper proves this with the fixed number 2⁷⁵, for any family at allSource 11.

A third paper applies these ideas to random graphs. It claims the graph-decomposition conjecture of Ascoli, He, Park and TalagrandSource 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 thresholdSource 13. Without splitting, the known bound loses a logarithmic factorSource 14. There is a catch. Each piece appears somewhere, but the copies need not fit together on shared pointsSource 15. That proof uses the discrete-convexity theorem as its main inputSource 16. The hard part was the links between points with many neighbors and points with fewSource 17. Knowing that a class of graphs is typical was not enough for that stepSource 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.