Family 186CombinatoricsNo LeanNot yet digested
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 , every nontrivial increasing relabeling-invariant property crosses from probability ε to within width for graphs and for r-uniform hypergraphs, r ≥ 3. The hypergraph influence bound also applies to nonmonotone properties.
Manuscripts in this family · 2
A uniform influence bound for hypergraph properties
Oct 5, 2026·hypergraph-influences.pdf
For every fixed integer r ≥ 3, we prove that every relabeling-invariant Boolean property of simple r-uniform hypergraphs on n vertices satisfies . The constant depends only on r, and the bound holds uniformly for all without a monotonicity assumption. For increasing properties, it gives the corresponding threshold-width bound with exponent , proving the hypergraph threshold-width conjecture of Friedgut and Kalai.
A Sharp Threshold Bound for Monotone Graph Properties
Sep 25, 2026·paper.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 , the edge probabilities at which its probability equals ε and differ by at most , for a universal constant C.