2018/09/28 by Nicholas A. Cook, Cook, Nicholas A., Amir Dembo +1 · 2 citations
Mathematics · #05C80 #60B20 #60C05 #60F10 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1809.11148
openalex publication_date 2018/09/28 · openalex created_date 2022/08/02 · openalex updated_date 2026/07/28
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.