Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913369429114880 |
|---|---|
| author | Kwan, Matthew Sah, Ashwin Sauermann, Lisa Sawhney, Mehtaab |
| author_facet | Kwan, Matthew Sah, Ashwin Sauermann, Lisa Sawhney, Mehtaab |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_02874 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture Kwan, Matthew Sah, Ashwin Sauermann, Lisa Sawhney, Mehtaab Combinatorics Probability 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. |
| title | Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2208.02874 |