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

DOI10.37236/9652zbMATH Open1467.05241arXiv1909.02308OpenAlexW3180755785MaRDI QIDQ2040004FDOQ2040004

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)

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.

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

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

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

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)

Cites Work

• Probability. Theory and examples.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Decomposition of graphical sequences and unigraphs
• Title not available (Why is that?)
• Fast uniform generation of regular graphs
• The splittance of a graph
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Sampling Regular Graphs and a Peer-to-Peer Network
• A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
• Title not available (Why is that?)
• The switch Markov chain for sampling irregular graphs and digraphs
• Towards random uniform sampling of bipartite graphs with given degree sequence
• A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix
• 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

Cited In (10)

• Random Seidel switching on graphs
• Graph classes and the switch Markov chain for matchings
• Title not available (Why is that?)
• Approximate sampling of graphs with near-\(P\)-stable degree intervals
• Mixing time of the swap Markov chain and \(P\)-stability
• Rapid mixing of the switch Markov chain for strongly stable degree sequences
• Mixing time of the switch Markov chain and stable degree sequences
• Approximate sampling and counting of graphs with near-regular degree intervals
• Fully graphic degree sequences and P-stable degree sequences
• On the swap-distances of different realizations of a graphical degree sequence

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)