check
Amir Dembo (Stanford), Large deviations of subgraph counts for sparse random graphs | Einstein Institute of Mathematics

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

Date: 
Tue, 27/11/201814:15-15:15
Location: 
Ross 70
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.