Optimal detection of planted stars via a random energy model
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 detection in $m$ in terms of the star size, and characterize the asymptotic total variation distance between the null and alternative hypotheses in this window. In the course of the proofs we show a condensation phase transition in the likelihood ratio that closely resembles that of the random energy model from spin glass theory.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.15585
curl -X POST /api/v1/records/arxiv/2602.15585/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.15585/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'