Sampling hypergraphs with given degrees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2021

Sampling hypergraphs with given degrees

Résumé

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.
Fichier principal
Vignette du fichier
2006.12021.pdf (268.99 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03474025 , version 1 (10-12-2021)

Identifiants

Citer

Martin Dyer, Catherine Greenhill, Pieter Kleer, James Ross, Leen Stougie. Sampling hypergraphs with given degrees. Discrete Mathematics, 2021, 344 (11), pp.1-14. ⟨10.1016/j.disc.2021.112566⟩. ⟨hal-03474025⟩

Collections

INRIA INRIA2
12 Consultations
67 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More