Moderate Deviations of Triangle Counts in the Erdős-Rényi Random Graph $G(n,m)$: The Lower Tail
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914124718407680 |
|---|---|
| author | Alvarado, José Dias, Gabriel Griffiths, Simon |
| author_facet | Alvarado, José Dias, Gabriel Griffiths, Simon |
| contents | Let $N_{\triangle}(G)$ be the number of triangles in a graph $G$. In [14] and [25] (respectively) the following bounds were proved on the lower tail behaviour of triangle counts in the dense Erdős-Rényi random graphs $G_m\sim G(n,m)$:
\[ \mathbb{P}\big(N_{\triangle}(G_m) \, < \, (1-δ)\mathbb{E}[N_{\triangle}(G_m)]\big) \,=\,
\exp\left(-Θ\left(δ^2n^3\right)\right) \qquad \text{if $n^{-3/2}\ll δ\ll n^{-1}$} \] and \[
\mathbb{P}\big(N_{\triangle}(G_m) \, < \, (1-δ)\mathbb{E}[N_{\triangle}(G_m)]\big) \,=\,
\exp\left(-Θ(δ^{2/3}n^2) \right) \qquad \text{if $n^{-3/4} \ll δ\ll 1$.}
\]
Neeman, Radin and Sadun [25] also conjectured that the probability should be of the form $\exp\left(-Θ\left(δ^2n^3\right)\right)$ in the "missing interval" $n^{-1}\ll δ\ll n^{-3/4}$. We prove this conjecture.
As part of our proof we also prove that some random graph statistics, related to degrees and codegrees, are normally distributed with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_13792 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Moderate Deviations of Triangle Counts in the Erdős-Rényi Random Graph $G(n,m)$: The Lower Tail Alvarado, José Dias, Gabriel Griffiths, Simon Combinatorics Probability Let $N_{\triangle}(G)$ be the number of triangles in a graph $G$. In [14] and [25] (respectively) the following bounds were proved on the lower tail behaviour of triangle counts in the dense Erdős-Rényi random graphs $G_m\sim G(n,m)$: \[ \mathbb{P}\big(N_{\triangle}(G_m) \, < \, (1-δ)\mathbb{E}[N_{\triangle}(G_m)]\big) \,=\, \exp\left(-Θ\left(δ^2n^3\right)\right) \qquad \text{if $n^{-3/2}\ll δ\ll n^{-1}$} \] and \[ \mathbb{P}\big(N_{\triangle}(G_m) \, < \, (1-δ)\mathbb{E}[N_{\triangle}(G_m)]\big) \,=\, \exp\left(-Θ(δ^{2/3}n^2) \right) \qquad \text{if $n^{-3/4} \ll δ\ll 1$.} \] Neeman, Radin and Sadun [25] also conjectured that the probability should be of the form $\exp\left(-Θ\left(δ^2n^3\right)\right)$ in the "missing interval" $n^{-1}\ll δ\ll n^{-3/4}$. We prove this conjecture. As part of our proof we also prove that some random graph statistics, related to degrees and codegrees, are normally distributed with high probability. |
| title | Moderate Deviations of Triangle Counts in the Erdős-Rényi Random Graph $G(n,m)$: The Lower Tail |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2403.13792 |