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

Kwan MA, Sah A, Sauermann L, Sawhney M. 2023. Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture. Forum of Mathematics, Pi. 11, e21.

Download

2023_ForumMathematics_Kwan.pdf
1.22 MB

*Journal Article*|

*Published*|

*English*

**Scopus indexed**

Author

Kwan, Matthew Alan

^{ISTA}^{}; Sah, Ashwin; Sauermann, Lisa; Sawhney, MehtaabDepartment

Abstract

An n-vertex graph is called C-Ramsey if it has no clique or independent set of size Clog2n (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 probability 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. In particular, a key ingredient is a new sharpened version of the quadratic Carbery–Wright theorem on small-ball probability for polynomials of Gaussians, which we believe is of independent interest. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay, for which Erdős reiterated in several of his open problem collections and for which he offered one of his notorious monetary prizes.

Keywords

Publishing Year

Date Published

2023-08-24

Journal Title

Forum of Mathematics, Pi

Acknowledgement

Kwan was supported for part of this work by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777. Sah and Sawhney were supported by NSF Graduate Research Fellowship Program DGE-2141064. Sah was supported by the PD Soros Fellowship. Sauermann was supported by NSF Award DMS-2100157, and for part of this work by a Sloan Research Fellowship.

Volume

11

Article Number

e21

ISSN

IST-REx-ID

### Cite this

Kwan MA, Sah A, Sauermann L, Sawhney M. Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture.

*Forum of Mathematics, Pi*. 2023;11. doi:10.1017/fmp.2023.17Kwan, M. A., Sah, A., Sauermann, L., & Sawhney, M. (2023). Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture.

*Forum of Mathematics, Pi*. Cambridge University Press. https://doi.org/10.1017/fmp.2023.17Kwan, Matthew Alan, Ashwin Sah, Lisa Sauermann, and Mehtaab Sawhney. “Anticoncentration in Ramsey Graphs and a Proof of the Erdős–McKay Conjecture.”

*Forum of Mathematics, Pi*. Cambridge University Press, 2023. https://doi.org/10.1017/fmp.2023.17.M. A. Kwan, A. Sah, L. Sauermann, and M. Sawhney, “Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture,”

*Forum of Mathematics, Pi*, vol. 11. Cambridge University Press, 2023.Kwan, Matthew Alan, et al. “Anticoncentration in Ramsey Graphs and a Proof of the Erdős–McKay Conjecture.”

*Forum of Mathematics, Pi*, vol. 11, e21, Cambridge University Press, 2023, doi:10.1017/fmp.2023.17.**All files available under the following license(s):**

**Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):**

**Main File(s)**

File Name

2023_ForumMathematics_Kwan.pdf
1.22 MB

Access Level

Open Access

Date Uploaded

2023-11-07

MD5 Checksum

54b824098d59073cc87a308d458b0a3e

### Export

Marked PublicationsOpen Data ISTA Research Explorer

### Sources

arXiv 2208.02874