University of Cambridge > > Combinatorics Seminar > Anticoncentration in Ramsey graphs and a proof of the Erdos-McKay conjecture

Anticoncentration in Ramsey graphs and a proof of the Erdos-McKay conjecture

Add to your list(s) Download to your calendar using vCal

  • UserMehtaab Sawhney (MIT)
  • ClockThursday 13 October 2022, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact ibl10.

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 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. One of the consequences of our result is the resolution of an old conjecture of Erdos and McKay, for which he offered one of his notorious monetary prizes.

(Joint work with Matthew Kwan, Ashwin Sah and Lisa Sauermann)

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity