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

DOI10.37236/9652MaRDI QIDQ2040004zbMATH OpenOpenAlexFDO

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

Publication date 6 July 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Monte Carlo Markov chain methodrandom graphs with a given degree sequence

Mathematics Subject Classification ID

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

Abstract: One of the simplest methods of generating a random graph with a given degree sequence is provided by the Monte Carlo Markov Chain method using switches. The switch Markov chain converges to the uniform distribution, but generally the rate of convergence is not known. After a number of results concerning various degree sequences, rapid mixing was established for so-called $P$-stable degree sequences (including that of directed graphs), which covers every previously known rapidly mixing region of degree sequences. In this paper we give a non-trivial family of degree sequences that are not $P$-stable and the switch Markov chain is still rapidly mixing on them. This family has an intimate connection to Tyshkevich-decompositions and strong stability as well.

Recommendations

• Rapid mixing of the switch Markov chain for strongly stable degree sequences
• Mixing time of the switch Markov chain and stable degree sequences
• Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices
• The mixing time of switch Markov chains: a unified approach
• The switch Markov chain for sampling irregular graphs and digraphs

Cites work

• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 747036 (Why is no real title available?)
• scientific article; zbMATH DE number 6472593 (Why is no real title available?)
• A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix
• A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
• Decomposition of graphical sequences and unigraphs
• Fast uniform generation of regular graphs
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Mixing time of the switch Markov chain and stable degree sequences
• Probability. Theory and examples.
• Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices
• Sampling Regular Graphs and a Peer-to-Peer Network
• The splittance of a graph
• The switch Markov chain for sampling irregular graphs and digraphs
• Towards random uniform sampling of bipartite graphs with given degree sequence

Cited in

(10)

• Mixing time of the swap Markov chain and \(P\)-stability
• Random Seidel switching on graphs
• Approximate sampling and counting of graphs with near-regular degree intervals
• Fully graphic degree sequences and P-stable degree sequences
• Graph classes and the switch Markov chain for matchings
• Rapid mixing of the switch Markov chain for strongly stable degree sequences
• On the swap-distances of different realizations of a graphical degree sequence
• scientific article; zbMATH DE number 7535774 (Why is no real title available?)
• Approximate sampling of graphs with near-\(P\)-stable degree intervals
• Mixing time of the switch Markov chain and stable degree sequences

This page was built for publication: Half-graphs, other non-stable degree sequences, and the switch Markov chain

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2040004)