The Lawlessness of Large Numbers

Abstraction: Finite Ramsey theory computation far harder than asymptotic bounds

Key points:

• Ramsey theory studies how large a set or graph can be before unavoidable patterns emerge; asymptotic results are often elegant, but finite exact values are notoriously intractable
• Kelley and Meka (2023) found a new asymptotic upper bound on progression-free sets, but this bound is not tight for small N; brute-force enumeration fails above N≈200 (more than 10^60 possible sets)
• Gasarch, Glenn, and Kruskal computed the largest progression-free sets up to N=187 in 2008 — a program that ran for months; randomized starting points outperform the greedy sequential algorithm
• The Ramsey number r(5,5) is still unknown, only bounded between 43 and 48; even r(3,10)≤42 required ~50 CPU-years to prove (Radziszowski and Goedgebeur, 2013)
• Brendan McKay's nauty software (1981) is essential for avoiding isomorphic graph rechecks; without it, Ramsey graph computation is computationally infeasible
• Techniques for generating extremal Ramsey graphs (random start + edge-deletion refinement) may transfer to other graph generation tasks such as chemical compound graphs

Connections: Ramsey Theory · Combinatorics · Computational Complexity

Source: https://www.wired.com/story/the-lawlessness-of-large-numbers/