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

Author: 

Goldschmidt, C
Griffiths, S
SCOTT, A

Publication Date: 

26 May 2020

Journal: 

Transactions of the American Mathematical Society

Last Updated: 

2021-06-11T23:10:52.493+01:00

DOI: 

10.1090/tran/8117

abstract: 

The main contribution of this article is an asymptotic expression for the
rate associated with moderate deviations of subgraph counts in the
Erd\H{o}s-R\'enyi 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.

Symplectic id: 

976067

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article