The statistical threshold for planted matchings and spanning trees

Louigi Addario-Berry, Omer Angel, Gábor Lugosi, Miklós Z. Rácz, Tselil Schramm

arXivarxiv/2602.07669Feb 7, 2026math.STscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2602.07669
curl -X POST /api/v1/records/arxiv/2602.07669/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.07669/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'