Mathematicians crack a 55-year-old conjecture using randomness
Researchers resolved Graham's conjecture — a combinatorics problem open since 1971 — by employing probabilistic methods that construct a mathematical structure through random selection and then prove it must possess the required property. The breakthrough continues a run of randomness-based proofs resolving problems that deterministic approaches had failed to crack.
- Graham's conjecture involves combinatorial number theory; Graham himself doubted it would be solved in his lifetime
- Probabilistic proof method has now cracked Hales-Jewett, Erdos discrepancy, and Graham's conjecture in succession
- Lead authors are in their 20s, continuing the pattern of major combinatorics breakthroughs from early-career mathematicians