Skip to main content.
Advanced search >
<< Back to previous page Print

<< Wednesday, October 10, 2018 >>

Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare

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

Seminar: Probability 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.