2018
Nov
27

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

2:15pm to 3:15pm

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