Sampling hypergraphs with given degrees

Martin Dyer, Catherine Greenhill*, Pieter Kleer, James Ross, Leen Stougie

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

Abstract

There is a well-known connection between hypergraphs and bipartite graphs, obtained by treating the incidence matrix of the hypergraph as the biadjacency matrix of a bipartite graph. We use this connection to describe and analyse a rejection sampling algorithm for sampling simple uniform hypergraphs with a given degree sequence. Our algorithm uses, as a black box, an algorithm A for sampling bipartite graphs with given degrees, uniformly or nearly uniformly, in (expected) polynomial time. The expected runtime of the hypergraph sampling algorithm depends on the (expected) runtime of the bipartite graph sampling algorithm A, and the probability that a uniformly random bipartite graph with given degrees corresponds to a simple hypergraph. We give some conditions on the hypergraph degree sequence which guarantee that this probability is bounded below by a positive constant. (C) 2021 Elsevier B.V. All rights reserved.
Original languageEnglish
Article number112566
Number of pages14
JournalDiscrete Mathematics
Volume344
Issue number11
DOIs
Publication statusPublished - Nov 2021

Keywords

  • Hypergraph
  • Degree sequence
  • Sampling
  • Algorithm
  • Markov chain
  • UNIFORM GENERATION
  • REGULAR GRAPHS
  • ALGORITHM

Fingerprint

Dive into the research topics of 'Sampling hypergraphs with given degrees'. Together they form a unique fingerprint.

Cite this