Local central limit theorem for triangle counts in sparse random graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917200084860928 |
|---|---|
| author | Araújo, Pedro Mattos, Letícia |
| author_facet | Araújo, Pedro Mattos, Letícia |
| contents | Let $X_H$ be the number of copies of a fixed graph $H$ in $G(n,p)$. In 2016, Gilmer and Kopparty conjectured that a local central limit theorem should hold for $X_H$ as long as $H$ is connected, $p\gg n^{-1/m(H)}$ and $n^2(1-p)\gg 1$, where $m(H)$ denotes the $m$-density of $H$. Recently, Sah and Sawhney showed that the Gilmer--Kopparty conjecture holds for constant $p$. In this paper, we show that the Gilmer--Kopparty conjecture holds for triangle counts in the sparse range. More precisely, if $p \in (4n^{-1/2}, 1/2)$, then $$\sup_{x\in \mathcal{L}}\left| \dfrac{1}{\sqrt{2π}}e^{-x^2/2}-σ\cdot \mathbb{P}(X^* = x)\right|=n^{-1/2+o(1)}p^{1/2},$$ where $σ^2 = \mathbb{V}\text{ar}(X_{K_3})$, $X^{*}=(X_{K_3}-\mathbb{E}(X_{K_3}))/σ$ and $\mathcal{L}$ is the support of $X^*$. By combining our result with the results of Röllin--Ross and Gilmer--Kopparty, this establishes the Gilmer--Kopparty conjecture for triangle counts for $n^{-1}\ll p < c$, for any constant $c\in (0,1)$. Our quantitative result is enough to prove that the triangle counts converge to an associated normal distribution also in the $\ell_1$-distance. This is the first local central limit theorem for subgraph counts above the so-called $m_2$-density threshold. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_09446 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Local central limit theorem for triangle counts in sparse random graphs Araújo, Pedro Mattos, Letícia Combinatorics Probability Let $X_H$ be the number of copies of a fixed graph $H$ in $G(n,p)$. In 2016, Gilmer and Kopparty conjectured that a local central limit theorem should hold for $X_H$ as long as $H$ is connected, $p\gg n^{-1/m(H)}$ and $n^2(1-p)\gg 1$, where $m(H)$ denotes the $m$-density of $H$. Recently, Sah and Sawhney showed that the Gilmer--Kopparty conjecture holds for constant $p$. In this paper, we show that the Gilmer--Kopparty conjecture holds for triangle counts in the sparse range. More precisely, if $p \in (4n^{-1/2}, 1/2)$, then $$\sup_{x\in \mathcal{L}}\left| \dfrac{1}{\sqrt{2π}}e^{-x^2/2}-σ\cdot \mathbb{P}(X^* = x)\right|=n^{-1/2+o(1)}p^{1/2},$$ where $σ^2 = \mathbb{V}\text{ar}(X_{K_3})$, $X^{*}=(X_{K_3}-\mathbb{E}(X_{K_3}))/σ$ and $\mathcal{L}$ is the support of $X^*$. By combining our result with the results of Röllin--Ross and Gilmer--Kopparty, this establishes the Gilmer--Kopparty conjecture for triangle counts for $n^{-1}\ll p < c$, for any constant $c\in (0,1)$. Our quantitative result is enough to prove that the triangle counts converge to an associated normal distribution also in the $\ell_1$-distance. This is the first local central limit theorem for subgraph counts above the so-called $m_2$-density threshold. |
| title | Local central limit theorem for triangle counts in sparse random graphs |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2307.09446 |