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. (Lean)

Manuscripts (2)

A uniform influence bound for hypergraph properties

October 5, 2026 · source · cite as \cite{OAI:A-uniform-influence-bound-for-hypergraph-properties-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.

A Sharp Threshold Bound for Monotone Graph Properties

September 25, 2026 · source · cite as \cite{OAI:A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties-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.

Result 186 · Combinatorics. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.