The statistical threshold for planted matchings and spanning trees
Louigi Addario-Berry, Omer Angel, Gábor Lugosi, Miklós Z. Rácz, Tselil Schramm · 2026
Read The statistical threshold for planted matchings and spanning trees by Louigi Addario-Berry, Omer Angel, Gábor Lugosi, Miklós Z. Rácz, Tselil Schramm (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-07669.txt.
Description
Can a statistician tell whether a random graph hides a planted matching or spanning tree? Louigi Addario-Berry and four co-authors study that detection problem for Erdős-Rényi graphs, with the option calibrated so edge counts alone cannot reveal the planting.
They prove a sharp threshold: when edge probability far exceeds n to the power minus one half, no test beats random guessing for either planted structure. Far below that threshold computationally efficient tests succeed with high probability. Random graph theorists get a clean statistical threshold for two canonical planted problems, with matching upper and lower bounds.
Catalog record
| CREATOR | Louigi Addario-Berry, Omer Angel, Gábor Lugosi, Miklós Z. Rácz, Tselil Schramm |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-07669