Strong Detection Threshold for Correlated Erdős-Rényi Graphs with Constant Average Degree
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918059909840896 |
|---|---|
| author | Feng, Chenxu |
| author_facet | Feng, Chenxu |
| contents | Consider a pair of correlated Erdős-Rényi graphs $\mathcal G(n,\tfracλ{n};s)$ that are subsampled from a common parent Erdős-Rényi graph with average degree $λ$ and subsampling probability $s$. We establish a sharp information-theoretic threshold for the detection problem between this model and two independent Erdős-Rényi graphs $\mathcal G(n,\tfracλ{n})$, showing that strong detection is information-theoretically possible if and only if $s>\min\{ \tfrac{1}{\sqrtλ}, \sqrtα \}$ where $α\approx 0.338$ is the Otter's constant. Our result resolves a constant gap between arXiv:2203.14573 and arXiv:2008.10097. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12752 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Strong Detection Threshold for Correlated Erdős-Rényi Graphs with Constant Average Degree Feng, Chenxu Probability 05C80 Consider a pair of correlated Erdős-Rényi graphs $\mathcal G(n,\tfracλ{n};s)$ that are subsampled from a common parent Erdős-Rényi graph with average degree $λ$ and subsampling probability $s$. We establish a sharp information-theoretic threshold for the detection problem between this model and two independent Erdős-Rényi graphs $\mathcal G(n,\tfracλ{n})$, showing that strong detection is information-theoretically possible if and only if $s>\min\{ \tfrac{1}{\sqrtλ}, \sqrtα \}$ where $α\approx 0.338$ is the Otter's constant. Our result resolves a constant gap between arXiv:2203.14573 and arXiv:2008.10097. |
| title | Strong Detection Threshold for Correlated Erdős-Rényi Graphs with Constant Average Degree |
| topic | Probability 05C80 |
| url | https://arxiv.org/abs/2506.12752 |