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

Abstract

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). In this paper, 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. This brings together two ongoing lines of research: the study of "random-like" properties of Ramsey graphs and the study of small-ball probabilities for low-degree polynomials of independent random variables. The proof proceeds via an "additive structure" dichotomy on the degree sequence, and involves a wide range of different tools from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics, and low-rank approximation. 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.

References in corpus (2)

• A Sub-Gaussian Berry-Esseen Theorem for the Hypergeometric Distribution
• Decoupling estimates in Fourier analysis