Mathematicians Discover New Way to Predict Structure in Graphs | Quanta Magazine

Abstraction: Ramsey number r(4,t) lower bound raised using finite geometry construction

Key points:

• Sam Mattheus (VUB/UCSD) and Jacques Verstraete proved a new lower bound for the asymmetric Ramsey number r(4,t), closing a 40+ year gap
• Prior best lower bound was ~t^(5/2) from the 1970s; the new result achieves ~t^3, matching the known upper bound from the 1930s
• Key innovation: using a Hermitian unital from finite geometry — an object well-known to geometers but never before applied to Ramsey problems
• The proof relied on pseudorandom graph constructions rather than the traditional fully random approach, representing a paradigm shift
• Result shows pure randomness has fundamental limits for Ramsey estimation; structured pseudorandom objects can outperform it
• Third major combinatorics breakthrough of early 2023, following symmetric Ramsey bounds and another big result

Connections: Ramsey Theory · Graph Theory · Combinatorics · Pseudorandom Graphs

Source: https://www.quantamagazine.org/mathematicians-discover-new-way-to-predict-structure-in-graphs-20230622/