# Sampling graphs with a given degree sequence

Last updated on
Mar 23, 2019

## Publications

### The mixing time of switch Markov chains: a unified approach

We show that the switch Markov chain is rapidly mixing on $P$-stable degree sequences of simple, bipartite, and directed graphs. …

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

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.

### Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs

Since 1997 a considerable effort has been spent on the study of the

**swap**(switch) Markov chains on graphic degree sequences. All of …## Talks

### On the mixing time of switch Markov chains

Generating graphs with a given degree sequence uniformly and randomly is a challenging problem. One of the popular methods is the switch Markov chain, which is a Markov chain Monte Carlo method that takes a random walk on the set of realizations via switches.

Oct 29, 2020 2:15 PM — 3:45 PM
Alfréd Rényi Insitute of Mathematics

### Mixing time of the swap Markov chain and P-stability (extended version)

Extended version of the talk of the same title given at EUROCOMB19

Nov 6, 2019 1:00 PM — 2:00 PM
University of Tasmania

### Mixing time of the swap Markov chain and P-stability

The aim of this paper is to confirm that $P$-stability of a family of unconstrained/bipartite/directed degree sequences is sufficient …

Aug 30, 2019 4:25 PM — 4:50 PM
Bratislava, Slovakia

### A non-stable bipartite degree sequence on which the swap Markov chain is rapidly mixing

The swap Markov chain on a bipartite degree sequence $d$ operates on realizations of $d$ by taking two-two vertices from each color …

Dec 13, 2018 2:15 PM — 3:45 PM
Alfréd Rényi Institute, Budapest