Probability and Mathematical Physics Seminar

Large deviations of subgraph counts for sparse random graphs

Speaker: Amir Dembo, Stanford University

Location: Warren Weaver Hall 1302

Date: Friday, October 25, 2019, 11:10 a.m.

Synopsis:

In this talk, based on joint works with Nick Cook and with Sohom Bhattacharya, I will discuss recent developments in the emerging theory of nonlinear large deviations, focusing on sharp upper tails for counts of several fixed subgraphs in a large sparse random graph, such as Erdos–Renyi or uniformly d-regular. Time permitting, I will describe our quantitative versions of the regularity and counting lemmas, which are geared for the study of sparse random graphs in the large deviations regime, and what our results suggest regarding certain questions in extremal graph theory.