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
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