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\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 .
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties
curl -X POST /api/v1/records/openai-math/A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/A-Sharp-Threshold-Bound-for-Monotone-Graph-Properties/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
Updates: Sharing AI progress on mathematics (amazing!); and my lecture plansCombinatorics and moreOct 7, 2026
together with the conjectured extension to uniform hypergraphs . Unique Games and 2-to-1 Games. My 2018 post on the 2-to-2 Games Theorem discussed progress toward Khot’s conjectures and the issue of perfect completeness. The release announces a proof of the Unique Games Conjecture and, separately,…