Amir Dembo (Stanford), Large deviations of subgraph counts for sparse random graphs

For fixed t>1 and L>3 we establish sharp asymptotic formula for the log-probability that the number of cycles of length L in the Erdos - Renyi random graph G(N,p) exceeds its expectation by a factor t, assuming only that p >> log N/sqrt(N). In a narrower range of p=p(N) we obtain such sharp upper tail for general subgraph counts and for the Schatten norms of the corresponding adjacency matrices. In this talk, based on a joint work with Nick Cook, I will explain our approach, based on convex-covering and a new quantitative refinement of Szemeredi's regularity lemma for sparse random graphs in the large deviations regime.


Tue, 27/11/2018 - 14:15 to 15:15


Ross 70