Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices

DOI10.1137/1.9781611975482.60zbMath1431.60073arXiv1803.01338OpenAlexW2953169267MaRDI QIDQ5236244

Georgios Amanatidis, Pieter Kleer

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Related Items (8)

Mixing time of the switch Markov chain and stable degree sequences ⋮ Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs ⋮ Cutoff for rewiring dynamics on perfect matchings ⋮ Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs ⋮ The mixing time of switch Markov chains: a unified approach ⋮ Half-graphs, other non-stable degree sequences, and the switch Markov chain ⋮ An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem ⋮ Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices

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