Sharp detection boundaries on testing dense subhypergraph

  • 2021-01-12 16:31:47
  • Mingao Yuan, Zuofeng Shang
  • 0


We study the problem of testing the existence of a dense subhypergraph. Thenull hypothesis is an Erdos-Renyi uniform random hypergraph and the alternativehypothesis is a uniform random hypergraph that contains a dense subhypergraph.We establish sharp detection boundaries in both scenarios: (1) the edgeprobabilities are known; (2) the edge probabilities are unknown. In bothscenarios, sharp detectable boundaries are characterized by the appropriatemodel parameters. Asymptotically powerful tests are provided when the modelparameters fall in the detectable regions. Our results indicate that thedetectable regions for general hypergraph models are dramatically differentfrom their graph counterparts.


Quick Read (beta)

loading the full paper ...