Threshold widths of increasing symmetric graph properties
Follow the latest progress by email.
How narrow is the transition of a nontrivial increasing graph property on n≥2 vertices that is invariant under relabeling? For 0<ε<1/2, the target width between probabilities ε and 1−ε is O(log(1/(2ε))/(log n)²).
Why it matters and what counts as progress
Why it matters: The squared-log scale quantifies how abruptly symmetric increasing graph properties appear in a random graph.
What counts as progress: Improve the previous 1/log n scale to the conjectured squared-log scale or obtain sharp constants and extremal properties.
How the problem developed
- 1996 · Bound and conjecture [1]
Ehud Friedgut and Gil Kalai Proved an O(log(1/ε)/log n) transition-width bound for symmetric monotone properties and conjectured the sharper squared-log scale.
- 25 Sept 2026 · Reported claim [2]
OpenAI The preprint reports a universal O(log(1/(2ε))/(log n)²) width bound for every nontrivial increasing relabeling-invariant graph property.
AI contribution
A Sharp Threshold Bound for Monotone Graph Properties
For every nontrivial increasing graph property on n≥2 vertices invariant under relabeling and 0<ε<1/2, the probability width from ε to 1−ε is at most 2¹⁹ log(1/(2ε))/(log n)².
Sources
Website timeline
Publication dates and editorial changes.