Journal article

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

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.

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Cite

Cite this record

APA Style

Goldschmidt, C., Griffiths, S., & Scott, A. (2020). Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p). Transactions of the American Mathematical Society, 373(2020), 5517–5585.

MLA Style

Goldschmidt, C., et al. “Moderate Deviations of Subgraph Counts in the Erdős-Rényi Random Graphs G(n,m) and G(n,p).” Transactions of the American Mathematical Society, vol. 373, no. 2020, American Mathematical Society, 2020, pp. 5517–85.

Chicago Style

Goldschmidt, C, Simon Griffiths, and A Scott. 2020. “Moderate Deviations of Subgraph Counts in the Erdős-Rényi Random Graphs G(n,m) and G(n,p).” Transactions of the American Mathematical Society 373 (2020): 5517–85.
Share
Print

Access Document

Files:: GoldschmidtetalAAM2020

(Accepted manuscript, 590.2KB, Terms of use)

Publisher copy:: 10.1090/tran/8117

Authors

+ Goldschmidt, C More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Statistics
Sub department:: Statistics
Role:: Author
ORCID:: 0000-0003-2750-6848

+ Simon Griffiths More by this author

Role:: Author

+ Scott, A More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Mathematical Institute
Sub department:: Mathematical Institute
Role:: Author

Publisher:: American Mathematical Society
Journal:: Transactions of the American Mathematical Society More from this journal
Volume:: 373
Issue:: 2020
Pages:: 5517-5585
Publication date:: 2020-05-26
Acceptance date:: 2020-02-03
DOI:: 10.1090/tran/8117
EISSN:: 1088-6850
ISSN:: 0002-9947

Language:: English
Keywords:: math.CO

FFR

math.PR
Pubs id:: 976067
Local pid:: pubs:976067
Deposit date:: 2020-02-08

Terms of use

Copyright holder:: American Mathematical Society
Copyright date:: 2020
Rights statement:: © Copyright 2020 American Mathematical Society
Notes:: This is the accepted manuscript version of the article. The final version is available from American Mathematical Society at: https://doi.org/10.1090/tran/8117

Licence:: Terms and Conditions of Use for Oxford University Research Archive

Views and Downloads

About views and downloads

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP