Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p)
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 martingal...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
American Mathematical Society
2020
|
| _version_ | 1797078988528549888 |
|---|---|
| author | Goldschmidt, C Simon Griffiths Scott, A |
| author_facet | Goldschmidt, C Simon Griffiths Scott, A |
| author_sort | Goldschmidt, C |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T00:39:14Z |
| format | Journal article |
| id | oxford-uuid:82787811-deea-46a4-9595-8a4f42d6cb43 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:39:14Z |
| publishDate | 2020 |
| publisher | American Mathematical Society |
| record_format | dspace |
| spelling | oxford-uuid:82787811-deea-46a4-9595-8a4f42d6cb432022-03-26T21:37:38ZModerate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p)Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:82787811-deea-46a4-9595-8a4f42d6cb43EnglishSymplectic ElementsAmerican Mathematical Society2020Goldschmidt, CSimon GriffithsScott, AThe 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. |
| spellingShingle | Goldschmidt, C Simon Griffiths Scott, A Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p) |
| title | Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p) |
| title_full | Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p) |
| title_fullStr | Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p) |
| title_full_unstemmed | Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p) |
| title_short | Moderate deviations of subgraph counts in the Erdős-Rényi random graphs G(n,m) and G(n,p) |
| title_sort | moderate deviations of subgraph counts in the erdos renyi random graphs g n m and g n p |
| work_keys_str_mv | AT goldschmidtc moderatedeviationsofsubgraphcountsintheerdosrenyirandomgraphsgnmandgnp AT simongriffiths moderatedeviationsofsubgraphcountsintheerdosrenyirandomgraphsgnmandgnp AT scotta moderatedeviationsofsubgraphcountsintheerdosrenyirandomgraphsgnmandgnp |