BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Combinatorics Seminar
SUMMARY:Anticoncentration in Ramsey graphs and a proof of
the Erdos-McKay conjecture - Mehtaab Sawhney (MIT
)
DTSTART;TZID=Europe/London:20221013T143000
DTEND;TZID=Europe/London:20221013T153000
UID:TALK183929AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/183929
DESCRIPTION: An $n$-vertex graph is called $C$-Ramsey if it ha
s 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 Ramse
y graphs\, in particular obtaining very precise co
ntrol of the distribution of the number of edges i
n a random vertex subset of a $C$-Ramsey graph. Th
is 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 vari
ables.\n\nThe proof proceeds via an ``additive str
ucture'' dichotomy on the degree sequence\, and in
volves a wide range of different tools from Fourie
r analysis\, random matrix theory\, the theory of
Boolean functions\, probabilistic combinatorics\,
and low-rank approximation. One of the consequence
s of our result is the resolution of an old conjec
ture of Erdos and McKay\, for which he offered one
of his notorious monetary prizes.\n\n(Joint work
with Matthew Kwan\, Ashwin Sah and Lisa Sauermann)
\n
LOCATION:MR12
CONTACT:
END:VEVENT
END:VCALENDAR