Uniform influence and sharp thresholds for graph and hypergraph properties
OpenAI research collection · 2 manuscripts · Source checked 2026-10-19
OpenAI's result summary
Proves the Friedgut–Kalai threshold-width conjectures for graphs and fixed-uniformity hypergraphs. For fixed 0< ε< 1/2, every nontrivial increasing relabeling-invariant property crosses from probability ε to 1-ε 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.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
A uniform influence bound for hypergraph properties
For every fixed integer r ≥ 3, we prove that every relabeling-invariant Boolean property of simple r-uniform hypergraphs on n vertices satisfies \mathop{Var}\nolimits _p(f)≤ C_r I_p(f)/(log n)^{r/(r-1)}. The constant depends only on r, and the bound holds uniformly for all 0< p< 1 without a monotonicity assumption. For…
Full source abstract
For every fixed integer r ≥ 3, we prove that every relabeling-invariant Boolean property of simple r-uniform hypergraphs on n vertices satisfies \mathop{Var}\nolimits _p(f)≤ C_r I_p(f)/(log n)^{r/(r-1)}. The constant depends only on r, and the bound holds uniformly for all 0< p< 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.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
A Sharp Threshold Bound for Monotone Graph Properties
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< ε< 1/2, the edge probabilities at which its probability equals ε and 1-ε differ by at most Clog(1/(2ε))/(log n)^2, for a universal…
Full source 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< ε< 1/2, the edge probabilities at which its probability equals ε and 1-ε differ by at most Clog(1/(2ε))/(log n)^2, for a universal constant C.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.