Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices

DOI10.1137/20M1352697zbMath1483.60101OpenAlexW4205192514MaRDI QIDQ5020837

Pieter Kleer, Georgios Amanatidis

Publication date: 7 January 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1352697

zbMATH Keywords

switch Markov chainjoint degree matrixgraph sampling

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On realizations of a joint degree matrix
• Fast uniform generation of regular graphs
• Relations between graphs and integer-pair sequences
• The switch Markov chain for sampling irregular graphs and digraphs
• The flip Markov chain for connected regular graphs
• Connected realizations of joint-degree matrices
• Towards random uniform sampling of bipartite graphs with given degree sequence
• The mixing time of switch Markov chains: a unified approach
• Graph realizations constrained by skeleton graphs
• Random bichromatic matchings
• Approximating the Permanent
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• On the Switch Markov Chain for Perfect Matchings
• Rapid mixing of the switch Markov chain for strongly stable degree sequences
• 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
• Constructing and sampling graphs with a prescribed joint degree distribution
• Sampling Regular Graphs and a Peer-to-Peer Network
• A Mountain-Climbing Problem
• A theorem on continuous functions

This page was built for publication: Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices