Item

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
$\mathcal{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 $\mathcal{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 constant.