Sharp detection boundaries on testing dense subhypergraph

Mingao Yuan, Zuofeng Shang

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

We study the problem of testing the existence of a dense subhypergraph. The null hypothesis corresponds to an Erdős-Rényi uniform random hypergraph and the alternative hypothesis corresponds to a uniform random hypergraph that contains a dense subhypergraph. We establish sharp detection boundaries in both scenarios: (1) the edge probabilities are known; (2) the edge probabilities are unknown. In both scenarios, sharp detection boundaries are characterized by the appropriate model parameters. Asymptotically powerful tests are provided when the model parameters fall in the detectable regions. Our results indicate that the detectable regions for general hypergraph models are dramatically different from their graph counterparts.

Original languageEnglish (US)
Pages (from-to)2459-2491
Number of pages33
JournalBernoulli
Volume28
Issue number4
DOIs
StatePublished - Nov 2022

All Science Journal Classification (ASJC) codes

  • Statistics and Probability

Keywords

  • asymptotically powerful test
  • dense subhypergraph detection
  • Sharp detection boundary
  • uniform hypergraph

Fingerprint

Dive into the research topics of 'Sharp detection boundaries on testing dense subhypergraph'. Together they form a unique fingerprint.

Cite this