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

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.

### Duke Scholars

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Related Subject Headings

- General Mathematics
- 0101 Pure Mathematics

### Citation

*Advances in Mathematics*,

*373*. https://doi.org/10.1016/j.aim.2020.107289

*Advances in Mathematics*373 (October 28, 2020). https://doi.org/10.1016/j.aim.2020.107289.

*Advances in Mathematics*, vol. 373, Oct. 2020.

*Scopus*, doi:10.1016/j.aim.2020.107289.

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Related Subject Headings

- General Mathematics
- 0101 Pure Mathematics