Browse › Combinatorics › 186 Uniform influence and sharp thresholds for graph and hypergraph properties
A uniform influence bound for hypergraph properties
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
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{\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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Comments and discussion
- Gil Kalai, Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans (Combinatorics and more, 2026-10-07). Item 17 covers the Friedgut–Kalai sharp-threshold result "together with the conjectured extension to uniform hypergraphs" and links it to his earlier exposition of sharp thresholds and symmetry; the post does not assess the proof, and none of the comments discuss this result. [family-level]
Formalization
- OpenAI math release, Lean scope notes for family 186 (lean/docs/186.md) (release Lean documentation, 2026-10-06). The family's Lean scope note lists only the graph companion paper and its threshold-width theorem; the r-uniform bound of this paper is not among its stated results. [family-level]
Related prior literature mentioned by others
- Gil Kalai, Boolean Functions: Influence, threshold and noise (7ECM lecture write-up, posted January 24, 2017). Kalai points to this survey in his October 2026 discussion of both papers; Sections 5.1–5.2 explain sharp thresholds and influence bounds under symmetry, including the earlier Bourgain–Kalai graph-property estimate. [family-level]
Possibly relevant literature (found by the agent, not checked)
- R. Rossignol, Threshold for monotone symmetric properties through a logarithmic Sobolev inequality (arXiv:math/0511607; Ann. Probab. 34(5), 2006). The paper improves the general threshold-width bound for monotone properties with transitive symmetry, the edge-transitivity baseline the introduction contrasts with the vertex-symmetry bound of Corollary 4.1.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 186
Independent sites; their content is not reviewed here.
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}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/186.md. The Lean statements have not been checked by people against the paper's claims.
Family 186: 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.
Other papers in this family:
- A Sharp Threshold Bound for Monotone Graph Properties · September 25, 2026