Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2602.07669 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912887855906816 |
|---|---|
| author | Addario-Berry, Louigi Angel, Omer Lugosi, Gábor Rácz, Miklós Z. Schramm, Tselil |
| author_facet | Addario-Berry, Louigi Angel, Omer Lugosi, Gábor Rácz, Miklós Z. Schramm, Tselil |
| contents | In this paper, we study the problem of detecting the presence of a planted perfect matching or spanning tree in an Erdős--Rényi random graph. More precisely, we study the hypothesis testing problem where the statistician observes a graph on $n$ vertices. Under the null hypothesis, the graph is a realization of an Erdős--Rényi random graph $G(n,q)$, while under the alternative hypothesis, the graph is the union of an Erdős--Rényi random graph and a random perfect matching (or random spanning tree). In order to avoid trivial detection by counting edges, we adjust the alternative hypothesis so that the expected number of edges under both distributions coincides. We prove that in both problems, when $q\gg n^{-1/2}$, no test can perform better than random guessing, while for $q\ll n^{-1/2}$, there exist computationally efficient tests that guess correctly with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_07669 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The statistical threshold for planted matchings and spanning trees Addario-Berry, Louigi Angel, Omer Lugosi, Gábor Rácz, Miklós Z. Schramm, Tselil Statistics Theory In this paper, we study the problem of detecting the presence of a planted perfect matching or spanning tree in an Erdős--Rényi random graph. More precisely, we study the hypothesis testing problem where the statistician observes a graph on $n$ vertices. Under the null hypothesis, the graph is a realization of an Erdős--Rényi random graph $G(n,q)$, while under the alternative hypothesis, the graph is the union of an Erdős--Rényi random graph and a random perfect matching (or random spanning tree). In order to avoid trivial detection by counting edges, we adjust the alternative hypothesis so that the expected number of edges under both distributions coincides. We prove that in both problems, when $q\gg n^{-1/2}$, no test can perform better than random guessing, while for $q\ll n^{-1/2}$, there exist computationally efficient tests that guess correctly with high probability. |
| title | The statistical threshold for planted matchings and spanning trees |
| topic | Statistics Theory |
| url | https://arxiv.org/abs/2602.07669 |