oai-math-revised beta

Browse › Combinatorics › 175 Talagrand’s expectation thresholds, discrete convexity, and graph decompositions

Talagrand’s discrete-convexity conjecture

OpenAI · September 23, 2026

Lean

Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion

Edit NOTES.md · Existing issues · Source on GitHub

Abstract

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.

If the PDF does not display here, open it directly: Open PDF.

Notes

No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.

Automatically collected notes (unreviewed)

work in progress

Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.

Formalization

  • OpenAI, Family 175 Lean scope note (lean/docs/175.md) (OpenAI Math Release, Oct 2026). States that the formalization proves the original-density discrete-convexity assertion with $k=2^{75}$ for arbitrary families and $0<p<1$, allowing repeated members in unions and requiring covering cost at most $1/2$, and links the comparator statement TalagrandDiscreteConvexity.lean. [family-level]

Possibly relevant literature (found by the agent, not checked)

  • Michel Talagrand, The Status of my favorite problems (author's website, 2026). Section 3 restates the discrete convexity question as Problem 3.3, says "sadly, it remains open", and surveys Li's and Park's recent results, giving context for Theorem 1.1 and Corollary 1.2.
  • Jinyoung Park, Michel Talagrand, AI's solution of Conjecture 9.1 (arXiv:2609.33644, 27 Sep 2026). Writes up an AI-generated proof of another conjecture from Talagrand's "Are many small sets explicitly small?"; Talagrand's status note places it within a projection-based approach to the two-union problem that Corollary 1.2 addresses. [AI-generated per source]

Digests and expositions

  • Open Mathematics Courses, Thresholds and expectation thresholds (undated). This eight-lesson course includes expositions of the three manuscripts, with proofs, examples and exercises, and identifies its author and self-checker as Claude Opus 5.5 with independent review incomplete. [AI-generated per source] [family-level]

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:Talagrands-discrete-convexity-conjecture-September-23-2026,
  author = {{OpenAI}},
  title = {{Talagrand's discrete-convexity conjecture}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Talagrands-discrete-convexity-conjecture-September-23-2026/paper.pdf}{OAI:Talagrands-discrete-convexity-conjecture-September-23-2026}},
  year = {2026}
}

Lean formalization

OpenAI provides Lean files for this family: lean/docs/175.md. The Lean statements have not been checked by people against the paper's claims.

Family 175: 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.

Other papers in this family: