The mixing time of switch Markov chains: a unified approach
From MaRDI portal
Publication:2237855
DOI10.1016/j.ejc.2021.103421zbMath1476.60116arXiv1903.06600OpenAlexW4288415043MaRDI QIDQ2237855
István Miklós, Tamás Róbert Mezei, Catherine Greenhill, Péter L. Erdős, Daniel Soltész, Lajos Soukup
Publication date: 28 October 2021
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1903.06600
Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Vertex degrees (05C07)
Related Items
Moments of Uniform Random Multigraphs with Fixed Degree Sequences ⋮ Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs ⋮ Cutoff for rewiring dynamics on perfect matchings ⋮ Approximate sampling of graphs with near-\(P\)-stable degree intervals ⋮ Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices
Cites Work
- Unnamed Item
- Unnamed Item
- A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
- A theorem on flows in networks
- Enumeration of graphs with a heavy-tailed degree sequence
- Fast uniform generation of regular graphs
- Polynomial-time counting and sampling of two-rowed contingency tables
- The switch Markov chain for sampling irregular graphs and digraphs
- Towards random uniform sampling of bipartite graphs with given degree sequence
- On counting perfect matchings in general graphs
- Algorithms for constructing graphs and digraphs with given valences and factors
- Mixing time of the switch Markov chain and stable degree sequences
- Uniform Sampling of Digraphs with a Fixed Degree Sequence
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Approximating the Permanent
- A remark on the existence of finite graphs
- Combinatorial Properties of Matrices of Zeros and Ones
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Uniform generation of random graphs with power-law degree sequences
- On the Switch Markov Chain for Perfect Matchings
- Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
- On the Swap-Distances of Different Realizations of a Graphical Degree Sequence
- 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
- The switch Markov chain for sampling irregular graphs (Extended Abstract)
- Statistical problems involving permutations with restricted positions
- Sampling Regular Graphs and a Peer-to-Peer Network
- Sampling binary contingency tables with a greedy start
