Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2503.08984 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911086404435968 |
|---|---|
| author | Gaudio, Julia Sandon, Colin Xu, Jiaming Yang, Dana |
| author_facet | Gaudio, Julia Sandon, Colin Xu, Jiaming Yang, Dana |
| contents | This paper studies the problem of inferring a $k$-factor, specifically a spanning $k$-regular graph, planted within an Erdos--Renyi random graph $G(n,λ/n)$. We uncover an interesting "all-something-nothing" phase transition. Specifically, we show that as the average degree $λ$ surpasses the critical threshold of $1/k$, the inference problem undergoes a transition from almost exact recovery ("all" phase) to partial recovery ("something" phase). Moreover, as $λ$ tends to infinity, the accuracy of recovery diminishes to zero, leading to the onset of the "nothing" phase. This finding complements the recent result by Mossel, Niles-Weed, Sohn, Sun, and Zadik who established that for certain sufficiently dense graphs, the problem undergoes an "all-or-nothing" phase transition, jumping from near-perfect to near-zero recovery. In addition, we characterize the recovery accuracy of a linear-time iterative pruning algorithm and show that it achieves almost exact recovery when $λ< 1/k$. A key component of our analysis is a two-step cycle construction: we first build trees through local neighborhood exploration and then connect them by sprinkling using reserved edges. Interestingly, for proving impossibility of almost exact recovery, we construct $Θ(n)$ many small trees of size $Θ(1)$, whereas for establishing the algorithmic lower bound, a single large tree of size $Θ(\sqrt{n\log n})$ suffices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_08984 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | "All-Something-Nothing" Phase Transitions in Planted k-Factor Recovery Gaudio, Julia Sandon, Colin Xu, Jiaming Yang, Dana Probability Statistics Theory This paper studies the problem of inferring a $k$-factor, specifically a spanning $k$-regular graph, planted within an Erdos--Renyi random graph $G(n,λ/n)$. We uncover an interesting "all-something-nothing" phase transition. Specifically, we show that as the average degree $λ$ surpasses the critical threshold of $1/k$, the inference problem undergoes a transition from almost exact recovery ("all" phase) to partial recovery ("something" phase). Moreover, as $λ$ tends to infinity, the accuracy of recovery diminishes to zero, leading to the onset of the "nothing" phase. This finding complements the recent result by Mossel, Niles-Weed, Sohn, Sun, and Zadik who established that for certain sufficiently dense graphs, the problem undergoes an "all-or-nothing" phase transition, jumping from near-perfect to near-zero recovery. In addition, we characterize the recovery accuracy of a linear-time iterative pruning algorithm and show that it achieves almost exact recovery when $λ< 1/k$. A key component of our analysis is a two-step cycle construction: we first build trees through local neighborhood exploration and then connect them by sprinkling using reserved edges. Interestingly, for proving impossibility of almost exact recovery, we construct $Θ(n)$ many small trees of size $Θ(1)$, whereas for establishing the algorithmic lower bound, a single large tree of size $Θ(\sqrt{n\log n})$ suffices. |
| title | "All-Something-Nothing" Phase Transitions in Planted k-Factor Recovery |
| topic | Probability Statistics Theory |
| url | https://arxiv.org/abs/2503.08984 |