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
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 590.2KB, Terms of use)
-
- Publisher copy:
- 10.1090/tran/8117
Authors
- 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:
- EISSN:
-
1088-6850
- ISSN:
-
0002-9947
- Language:
-
English
- Keywords:
- Pubs id:
-
976067
- Local pid:
-
pubs:976067
- Deposit date:
-
2020-02-08
- ARK identifier:
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
If you are the owner of this record, you can report an update to it here: Report update to this record