Uniform influence and sharp thresholds for graph and hypergraph properties

2 papersLean

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.

Watch

The problem

What is being asked, where it comes from, and why it is hard. No proof needed.

▶Introduction to the problemin preparation

The solution proposed by OpenAI

How the paper solves it, step by step.

Full explanation

▶The proposed solutionin preparation

Papers 2

A uniform influence bound for hypergraph properties

OpenAI · October 5, 2026

For every fixed integer r ≥ 3, we prove that every relabeling-invariant Boolean property of simple r-uniform hypergraphs on n vertices satisfies \(\mathop{\mathrm{Var}}\nolimits _p(f)\le C_r I_p(f)/(\log n)^{r/(r-1)}\). The constant depends only on r, and the bound holds uniformly for all \(0\lt p\lt 1\) without a monotonicity assumption. For increasing properties, it gives the corresponding threshold-width bound with exponent \(r/(r-1)\), proving the hypergraph threshold-width conjecture of Friedgut and Kalai.

Read PDF Download Source

Cite

@misc{OAI:A-uniform-influence-bound-for-hypergraph-properties-October-5-2026,
  author = {{OpenAI}},
  title = {{A uniform influence bound for hypergraph properties}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/A-uniform-influence-bound-for-hypergraph-properties-October-5-2026/hypergraph-influences.pdf}{OAI:A-uniform-influence-bound-for-hypergraph-properties-October-5-2026}},
  year = {2026}
}

A Sharp Threshold Bound for Monotone Graph Properties

OpenAI · September 25, 2026

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.

Read PDF Download Source

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}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

A Sharp Threshold Bound for Monotone Graph Properties

Scope

The Friedgut–Kalai sharp-threshold conjecture concerns how quickly a nontrivial increasing graph property appears in the independent-edge random graph. For every \(n\ge2\), every such property invariant under vertex relabeling, and \(0<\varepsilon<1/2\), the formalization proves that the edge-probability interval between probabilities \(\varepsilon\) and \(1-\varepsilon\) has width at most \(2^{19}\log(1/(2\varepsilon))/(\log n)^2\). The constant is uniform over the graph property, \(n\), and \(\varepsilon\).

Comparator links

Result	Comparator statement
Sharp threshold width for monotone graph properties	SharpThreshold.lean

Scope note on GitHub →