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 (9)

• Inverse Littlewood-Offord problems and The Singularity of Random Symmetric Matrices
• Refined Estimates Concerning Sumsets Contained in the Roots of Unity
• Anticoncentration for subgraph statistics
• Combinatorial anti-concentration inequalities, with applications
• Random walks in Euclidean space
• An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
• A Sub-Gaussian Berry-Esseen Theorem for the Hypergeometric Distribution
• New inequalities for permanents and hafnians and some generalizations
• Decoupling estimates in Fourier analysis