Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2506.12752 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
Sommario:
- 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.