Optimal detection of planted stars via a random energy model

Ijay Narang, Will Perkins, Timothy L. H. Wee

We study the problem of detecting a planted star in the Erd{ő}s--R{é}nyi random graph $G(n,m)$, formulated as a hypothesis test. We determine the scaling window for critical dete…