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

Seminar | October 10 | 3-4 p.m. | 1011 Evans Hall

 Nicholas Cook, UCLA

 Department of Statistics

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 upper tail for general subgraph counts, as well as the lower tail for counts of seminorming graphs, in narrower ranges of sparsity. As in other recent works on the emerging theory of nonlinear large deviations, our general approach applies to functions on product spaces which are of ``low complexity", though the notion of complexity used here is somewhat different. Based on joint work with Amir Dembo.

 sganguly@berkeley.edu