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

Journal Article

© 2020 Elsevier Inc. For any fixed simple graph H=(V,E) and any fixed u>0, we establish the leading order of the exponential rate function for the probability that the number of copies of H in the Erdős–Rényi graph G(n,p) exceeds its expectation by a factor 1+u, assuming n−κ(H)≪p≪1, with κ(H)=1/(2Δ), where Δ≥1 is the maximum degree of H. This improves on a previous result of Chatterjee and the second author, who obtained κ(H)=c/(Δ|E|) for a constant c>0. Moreover, for the case of cycle counts we can take κ as large as 1/2. We additionally obtain the sharp upper tail for Schatten norms of the adjacency matrix, as well as the sharp lower tail for counts of graphs for which Sidorenko's conjecture holds. As a key step, we establish quantitative versions of Szemerédi's regularity lemma and the counting lemma, suitable for the analysis of random graphs in the large deviations regime.

Full Text

Duke Authors

Cited Authors

  • Cook, N; Dembo, A

Published Date

  • October 28, 2020

Published In

Volume / Issue

  • 373 /

Electronic International Standard Serial Number (EISSN)

  • 1090-2082

International Standard Serial Number (ISSN)

  • 0001-8708

Digital Object Identifier (DOI)

  • 10.1016/j.aim.2020.107289

Citation Source

  • Scopus