---
_id: '14499'
abstract:
- lang: eng
  text: "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.\r\n\r\nThe 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."
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.
article_number: e21
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Matthew Alan
  full_name: Kwan, Matthew Alan
  id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
  last_name: Kwan
  orcid: 0000-0002-4003-7567
- first_name: Ashwin
  full_name: Sah, Ashwin
  last_name: Sah
- first_name: Lisa
  full_name: Sauermann, Lisa
  last_name: Sauermann
- first_name: Mehtaab
  full_name: Sawhney, Mehtaab
  last_name: Sawhney
citation:
  ama: Kwan MA, Sah A, Sauermann L, Sawhney M. Anticoncentration in Ramsey graphs
    and a proof of the Erdős–McKay conjecture. <i>Forum of Mathematics, Pi</i>. 2023;11.
    doi:<a href="https://doi.org/10.1017/fmp.2023.17">10.1017/fmp.2023.17</a>
  apa: Kwan, M. A., Sah, A., Sauermann, L., &#38; Sawhney, M. (2023). Anticoncentration
    in Ramsey graphs and a proof of the Erdős–McKay conjecture. <i>Forum of Mathematics,
    Pi</i>. Cambridge University Press. <a href="https://doi.org/10.1017/fmp.2023.17">https://doi.org/10.1017/fmp.2023.17</a>
  chicago: Kwan, Matthew Alan, Ashwin Sah, Lisa Sauermann, and Mehtaab Sawhney. “Anticoncentration
    in Ramsey Graphs and a Proof of the Erdős–McKay Conjecture.” <i>Forum of Mathematics,
    Pi</i>. Cambridge University Press, 2023. <a href="https://doi.org/10.1017/fmp.2023.17">https://doi.org/10.1017/fmp.2023.17</a>.
  ieee: M. A. Kwan, A. Sah, L. Sauermann, and M. Sawhney, “Anticoncentration in Ramsey
    graphs and a proof of the Erdős–McKay conjecture,” <i>Forum of Mathematics, Pi</i>,
    vol. 11. Cambridge University Press, 2023.
  ista: 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.
  mla: Kwan, Matthew Alan, et al. “Anticoncentration in Ramsey Graphs and a Proof
    of the Erdős–McKay Conjecture.” <i>Forum of Mathematics, Pi</i>, vol. 11, e21,
    Cambridge University Press, 2023, doi:<a href="https://doi.org/10.1017/fmp.2023.17">10.1017/fmp.2023.17</a>.
  short: M.A. Kwan, A. Sah, L. Sauermann, M. Sawhney, Forum of Mathematics, Pi 11
    (2023).
date_created: 2023-11-07T09:02:48Z
date_published: 2023-08-24T00:00:00Z
date_updated: 2023-11-07T09:18:57Z
day: '24'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1017/fmp.2023.17
external_id:
  arxiv:
  - '2208.02874'
file:
- access_level: open_access
  checksum: 54b824098d59073cc87a308d458b0a3e
  content_type: application/pdf
  creator: dernst
  date_created: 2023-11-07T09:16:23Z
  date_updated: 2023-11-07T09:16:23Z
  file_id: '14500'
  file_name: 2023_ForumMathematics_Kwan.pdf
  file_size: 1218719
  relation: main_file
  success: 1
file_date_updated: 2023-11-07T09:16:23Z
has_accepted_license: '1'
intvolume: '        11'
keyword:
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Mathematical Physics
- Statistics and Probability
- Algebra and Number Theory
- Analysis
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
  grant_number: '101076777'
  name: Randomness and structure in combinatorics
publication: Forum of Mathematics, Pi
publication_identifier:
  issn:
  - 2050-5086
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2023'
...