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.
released 2026-10-05 | 1 theorem · 3 lemmas · 5 proofs · 2,765 words |
PLAY LEVEL 1 »(pdf)
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.
released 2026-09-25 | 2 theorems · 3 lemmas · 6 proofs · 3,365 words |
PLAY LEVEL 2 »(pdf)
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.