Mehtaab Sawhney, Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture

An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $C{\log }_{2}n$ (i.e., if it has near-optimal Ramsey behavior). We study edge-statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a $C$-Ramsey graph. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay, for which Erdős offered one of his notorious monetary prizes and the proof involves a wide range of different tools from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics, and low-rank approximation.

Joint w. Matthew Kwan, Ashwin Sah, and Lisa Sauermann