Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs

Péter L Erdős, Tamás Róbert Mezei, István Miklós and Dániel Soltész

PLOS ONE, 2018, vol. 13, issue 8, 1-20

Abstract: Since 1997 a considerable effort has been spent on the study of the swap (switch) Markov chains on graphic degree sequences. All of these results assume some kind of regularity in the corresponding degree sequences. Recently, Greenhill and Sfragara published a breakthrough paper about irregular normal and directed degree sequences for which rapid mixing of the swap Markov chain is proved. In this paper we present two groups of results. An example from the first group is the following theorem: let d → be a directed degree sequence on n vertices. Denote by Δ the maximum value among all in- and out-degrees and denote by | E → | the number of edges in the realization. Assume furthermore that Δ

Date: 2018
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0201995 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 01995&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0201995

DOI: 10.1371/journal.pone.0201995

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().