The Wrong Random Model

Erdős proved in 1947 that Ramsey numbers grow exponentially by coloring random graphs: if you color the edges of a random graph on n vertices, the probability that any particular set of k vertices forms a monochromatic clique is small enough that, for appropriate k, no such clique exists. The bound stood for 78 years. Spencer improved it by a constant factor in 1975. Nothing exponential changed.

The paper achieves the first exponential improvement. The key is replacing the random model. Erdős used Erdős-Rényi random graphs — each edge present independently with probability 1/2. The new construction uses a geometric model where edge presence depends on spatial relationships between vertices. This introduces correlations: edges are positively correlated with each other, and non-edges are negatively correlated with each other.

The correlations work in the right direction. Positive edge correlations make large cliques more likely than in the independent model — but the Ramsey lower bound doesn’t need cliques to be rare, it needs large monochromatic cliques in both colors simultaneously to be rare. The negative correlation among non-edges suppresses large independent sets (monochromatic cliques in the complementary color) more than the positive correlation enhances cliques in the primary color. The net effect: the geometric model avoids monochromatic cliques more efficiently than the independent model.

The structural point: the obstacle to improving Ramsey bounds was not the method (probabilistic) but the model (independent edges). The right random structure for Ramsey theory has correlations that the obvious model lacks. For 78 years, the random model was hiding the answer by being too symmetric.