Optimal detection of planted stars via a random energy model

Fuente: arXiv
Enregistré dans:
Détails bibliographiques
Auteurs principaux: Narang, Ijay, Perkins, Will, Wee, Timothy L. H.
Format: Preprint
Publié: 2026
Sujets:
Accès en ligne:
Tags: Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
_version_ 1866908837769904128
author Narang, Ijay
Perkins, Will
Wee, Timothy L. H.
author_facet Narang, Ijay
Perkins, Will
Wee, Timothy L. H.
contents 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.
format Preprint
id arxiv_https___arxiv_org_abs_2602_15585
institution arXiv
publishDate 2026
record_format arxiv
spellingShingle Optimal detection of planted stars via a random energy model
Narang, Ijay
Perkins, Will
Wee, Timothy L. H.
Statistics Theory
Information Theory
Probability
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.
title Optimal detection of planted stars via a random energy model
topic Statistics Theory
Information Theory
Probability
url https://arxiv.org/abs/2602.15585