Talagrand’s expectation thresholds, discrete convexity, and graph decompositions
OpenAI research collection · 3 manuscripts · Source checked 2026-10-19
OpenAI's result summary
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.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
Graph Decompositions at the Integral Expectation Threshold
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…
Full source abstract
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.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
Integral and fractional expectation thresholds are equivalent
We prove Talagrand's conjecture that integral and fractional expectation thresholds are within a universal constant factor, with the same covering budget.
This PDF is listed in OpenAI's formalization catalogue. See the scope and dependencies before interpreting coverage.
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.
This PDF is listed in OpenAI's formalization catalogue. See the scope and dependencies before interpreting coverage.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.