oai-math-revised beta

Browse › Combinatorics › 186 Uniform influence and sharp thresholds for graph and hypergraph properties

A Sharp Threshold Bound for Monotone Graph Properties

OpenAI · September 25, 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 the Friedgut–Kalai sharp-threshold conjecture. For every integer n ≥ 2, every nontrivial increasing family of graphs on n vertices invariant under all vertex permutations, and every $0\lt \varepsilon\lt 1/2$, the edge probabilities at which its probability equals ε and $1-\varepsilon$ differ by at most $C\log(1/(2\varepsilon))/(\log n)^2$, for a universal constant C.

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.

Follow-up works

  • OpenAI, A uniform influence bound for hypergraph properties (OpenAI Math Release preprint, 2026-10-05). The companion manuscript in the same release says it reproduces this paper's Fourier estimate and vertex-block restriction argument, and replaces the graph degree estimate with an r-uniform one to get the exponent r/(r-1). [AI-generated per source] [family-level]

Formalization

  • OpenAI math release, Lean scope notes for family 186 (lean/docs/186.md) (release Lean documentation, 2026-10-06). The scope note reports formalization of the threshold-width bound $2^{19}\log(1/(2\varepsilon))/(\log n)^2$ of Theorem 1.1, uniform over nontrivial increasing relabeling-invariant graph properties, $n\ge2$, and $0<\varepsilon<1/2$, checked against the comparator statement ComparatorChallenges/SharpThreshold.lean. [family-level]
  • Gil Kalai, Boolean Functions: Influence, threshold and noise (7ECM lecture write-up, posted January 24, 2017). Kalai points to this survey in his October 2026 discussion of both papers; Sections 5.1–5.2 explain sharp thresholds and influence bounds under symmetry, including the earlier Bourgain–Kalai graph-property estimate. [family-level]

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

Elsewhere

Independent sites; their content is not reviewed here.

Cite

@misc{OAI:A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties-September-25-2026,
  author = {{OpenAI}},
  title = {{A Sharp Threshold Bound for Monotone Graph Properties}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties-September-25-2026/paper.pdf}{OAI:A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties-September-25-2026}},
  year = {2026}
}

Lean formalization

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

Family 186: Uniform influence and sharp thresholds for graph and hypergraph properties

Proves the Friedgut–Kalai threshold-width conjectures for graphs and fixed-uniformity hypergraphs. For fixed $0\lt \varepsilon\lt 1/2$, every nontrivial increasing relabeling-invariant property crosses from probability ε to $1-\varepsilon$ within width $O((\log n)^{-2})$ for graphs and $O_r((\log n)^{-r/(r-1)})$ for r-uniform hypergraphs, r ≥ 3. The hypergraph influence bound also applies to nonmonotone properties.

Other papers in this family: