Large deviations of subgraph counts for sparse Erdős–Rényi graphs

By Nicholas A. Cook, Amir Dembo. Advances in Mathematics, 2018

73 citations recorded by the source corpus.

For each fixed integer $\ell\ge 3$ and $u>0$ we establish the leading order of the exponential rate function for the probability that the number of cycles of length $\ell$ in the Erdős--Renyi graph $G(N,p)$ exceeds its expectation by a factor $1+u$, 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 sharp upper tail for Schatten norms of the adjacency matrix, and for general subgraph counts in a narrower range of $p$, as well as the sharp lower tail for counts of seminorming graphs. As in recent works of Chatterjee--Dembo and Eldan on the emerging theory of \emph{nonlinear large deviations}, our general approach applies to "low complexity" functions on product spaces, though the notion of complexity used here is somewhat different. For the application to random graphs, our argument can be viewed as a quantitative refinement of the spectral approach to Szemeredi's regularity lemma for the setting of random graphs in the large deviations regime for counts of a given subgraph.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/2a03b09d7d3910a28ab101f16d3f3ec94f390faa

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

  1. Alice Guionnet
  2. F. Augeri

In Geometry and Topology

  1. Alice Guionnet

In Statistics and Probability

  1. Jonathan Husson
  2. Alice Guionnet
  3. F. Augeri
  4. Sourav Chatterjee
  5. L. Erdős
  6. Édouard Maurel-Segala
  7. Benoît Collins
  8. Horng-Tzer Yau

Citations in the corpus