Large deviations of subgraph counts for sparse Erd\H{o}s--R\'enyi graphs

Large deviations of subgraph counts for sparse Erd\H{o}s--R\'enyi graphs

Probability Seminar
Oct 10, 2018, 03:00 PM - 04:00 PM | 1011 Evans Hall | Happening As Scheduled
Nicholas Cook, UCLA
For each fixed integer $\ell\ge 3$ we establish the leading order of the exponential rate function for the probability that the number of cycles of length $\ell$ in the Erd\H{o}s--R\'enyi graph $G(N,p)$ exceeds its expectation by a constant factor, assuming $N^{-1/2}\ll p\ll 1$ (up to log corrections) when $\ell\ge 4$, and $N^{-1/3}\ll p\ll 1$ in the case of triangles. We additionally obtain the...