Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p)

2019/02/18 by Christina Goldschmidt, Goldschmidt, Christina, Simon Griffiths +3 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #Statistical Methods and Inference #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1902.06830

openalex publication_date 2019/02/18 · openalex created_date 2021/01/05 · openalex updated_date 2026/07/28

Abstract

The main contribution of this article is an asymptotic expression for the rate associated with moderate deviations of subgraph counts in the Erdős-Rényi random graph G(n,m). Our approach is based on applying Freedman's inequalities for the probability of deviations of martingales to a martingale representation of subgraph count deviations. In addition, we prove that subgraph count deviations of different subgraphs are all linked, via the deviations of two specific graphs, the path of length two and the triangle. We also deduce new bounds for the related G(n,p) model.

Cited by

• Tripodal structure in undersaturated random graphs

Related

• Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs G(n,m) and G(n,p)
• A large deviation principle for the Erdős-Rényi uniform random graph
• Moderate Deviations of Triangle Counts in the Erdős-Rényi Random Graph G(n,m): The Lower Tail
• Large deviations of subgraph counts for sparse Erdős--Rényi graphs
• Upper tail large deviations of regular subgraph counts in Erdős-Rényi graphs in the full localized regime