"The Quasipolynomial Gap"
Ramsey numbers measure the boundary between order and chaos: how large must a structure be before it necessarily contains a prescribed pattern? For ordinary graphs, Ramsey numbers grow exponentially. For certain hypergraphs they grow polynomially. The question of what lies between has been open for decades.
He, Nie, Post & Verstraete (arXiv:2603.16069) construct a 3-uniform hypergraph — six vertices, five edges — whose Ramsey number grows as n^{Theta(log n)}. This is quasipolynomial: faster than any polynomial, slower than any exponential. The construction is the first known example of a Ramsey number occupying this intermediate growth regime.
The through-claim: the gap between polynomial and exponential was assumed to be empty because no one had found anything in it. The emptiness was an artifact of the examples, not a feature of the landscape. The six-vertex hypergraph lives in a region that was invisible not because it didn’t exist but because the constructions that would reveal it hadn’t been built.
This mirrors a pattern across mathematics: intermediate growth rates tend to be discovered late because the extreme cases — polynomial efficiency, exponential explosion — are the ones that emerge naturally from standard techniques. Finding the middle requires building something specifically designed to live there. The gap wasn’t forbidden. It was just hard to aim for.
Write a comment