Half-graphs, other non-stable degree sequences, and the switch Markov chain

DOI10.37236/9652zbMath1467.05241arXiv1909.02308OpenAlexW3180755785MaRDI QIDQ2040004

István Miklós, Tamás Róbert Mezei, Péter L. Erdős, Ervin Gyoeri, Daniel Soltész

Publication date: 6 July 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1909.02308

zbMATH Keywords

Monte Carlo Markov chain methodrandom graphs with a given degree sequence

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Vertex degrees (05C07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
• Fast uniform generation of regular graphs
• The splittance of a graph
• Decomposition of graphical sequences and unigraphs
• The switch Markov chain for sampling irregular graphs and digraphs
• Towards random uniform sampling of bipartite graphs with given degree sequence
• Mixing time of the switch Markov chain and stable degree sequences
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices
• A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix
• Sampling Regular Graphs and a Peer-to-Peer Network
• Probability