{"id":"arxiv/2602.07669","url":"https://arxiv.org/abs/2602.07669","tags":["math.ST"],"score":0,"title":"The statistical threshold for planted matchings and spanning trees","domain":"math.ST","source":"arxiv","authors":["Louigi Addario-Berry","Omer Angel","Gábor Lugosi","Miklós Z. Rácz","Tselil Schramm"],"reviews":0,"subject":"math.ST","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-07","reactions":{}}