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.
released 2026-10-05 | 2 theorems · 3 lemmas · 8 proofs · 4,641 words |
PLAY LEVEL 1 »(pdf)
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.
released 2026-09-23 | 2 theorems · 1 lemma · 4 proofs · 4,430 words |
PLAY LEVEL 2 »(pdf)
We prove Talagrand's conjecture that integral and fractional expectation thresholds are within a universal constant factor, with the same covering budget.
released 2026-09-23 | 1 theorem · 1 lemma · 4 proofs · 3,404 words |
PLAY LEVEL 3 »(pdf)
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.