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

CREATORLouigi Addario-Berry, Omer Angel, Gábor Lugosi, Miklós Z. Rácz, Tselil Schramm
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-07669

Browse the full library · About the Tower of Babel