Large deviations in random graphs

Computer Science/Discrete Mathematics Seminar I
Topic:Large deviations in random graphs
Speaker:Eyal Lubetzky
Affiliation:New York University
Date:Monday, April 9
Time/Room:11:00am - 12:15pm/West Building Lecture Hall

What is the probability that the number of triangles in the Erd\H{o}s-R\'enyi random graph with edge density $p$, is at least twice its mean? What is the typical structure of the graph conditioned on this rare event? For instance, when $p=o(1)$, already obtaining the order of log of this probability was a longstanding open problem finally settled by Chatterjee and by DeMarco and Kahn, whereas the latter problem remains largely open. I will review some recent progress on these questions and related ones, in both the dense and sparse regimes of the random graph.