### New classes of degree sequences with fast mixing swap Markov chain sampling

**2016-01-29**

1601.08224 | math.CO

In network modeling of complex systems one is often required to sample random
realizations of networks that obey a given set of constraints, usually in form
of graph measures. A much studied class of problems targets uniform sampling of
simple graphs with given degree sequence or also with given degree correlations
expressed in the form of a joint degree matrix. One approach is to use Markov
chains based on edge switches (swaps) that preserve the constraints, are
irreducible (ergodic) and fast mixing. In 1999, Kannan, Tetali and Vempala
(KTV) proposed a simple swap Markov chain for sampling graphs with given degree
sequence and conjectured that it mixes rapidly (in poly-time) for arbitrary
degree sequences. While the conjecture is still open, it was proven for special
degree sequences, in particular, for those of undirected and directed regular
simple graphs, of half-regular bipartite graphs, and of graphs with certain
bounded maximum degrees. Here we prove the fast mixing KTV conjecture for
novel, exponentially large classes of irregular degree sequences. Our method is
based on a canonical decomposition of degree sequences into split graph degree
sequences, a structural theorem for the space of graph realizations and on a
factorization theorem for Markov chains. After introducing bipartite splitted
degree sequences, we also generalize the canonical split graph decomposition
for bipartite and directed graphs.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-05-08**

1905.06895 | cs.DS

We show that the graph transformation problem of turning a simple graph into
an Eulerian one by a mi… show more

**2019-01-28**

1901.09560 | math.CO

We investigate a covering problem in $3$-uniform hypergraphs ($3$-graphs):
given a $3$-graph $F$, wh… show more

**2019-03-15**

1903.06600 | math.CO

Since 1997 a considerable effort has been spent to study the mixing time of
\textbf{swap} (switch) M… show more

**2019-01-07**

1901.01861 | cs.DM

For every fixed integer $k \geq 1$, we prove that $k$-Edge Colouring is
fixed-parameter-tractable wh… show more

**2014-06-10**

1406.2587 | cs.SI

This research establishes that many real-world networks exhibit bounded
expansion, a strong notion o… show more

**2018-09-08**

1809.02835 | cs.DS

We consider the problem of determining the maximal $\alpha \in (0,1]$ such
that every matching $M$ o… show more

**2018-12-07**

1812.03195 | cs.DM

We show that a simple Markov chain, the Glauber dynamics, can efficiently
sample independent sets al… show more

**2018-02-11**

1802.03727 | math.CO

We study a restricted form of list colouring, for which every pair of lists
that correspond to adjac… show more

**2019-04-26**

1904.11861 | math.PR

We study the following preferential attachment variant of the classical
Erdos-Renyi random graph pro… show more

**2018-03-04**

1803.01338 | cs.DM

The switch Markov chain has been extensively studied as the most natural
Markov Chain Monte Carlo ap… show more

**2018-07-12**

1807.04803 | math.CO

A maximal $\varepsilon$-near perfect matching is a maximal matching which
covers at least $(1-\varep… show more

**2018-09-14**

1809.05443 | cs.DM

A graph $G$ realizes the degree sequence $S$ if the degrees of its vertices
is $S$. Hakimi gave a ne… show more

**2018-08-07**

1808.02512 | math.CO

Any triangle-free graph on $n$ vertices with minimum degree at least $d$
contains a bipartite induce… show more

**2019-03-04**

1903.01342 | math.PR

We establish and generalise several bounds for various random walk quantities
including the mixing t… show more

**2017-06-13**

1706.03951 | math.OC

We introduce and study the problem of optimizing arbitrary functions over
degree sequences of hyperg… show more

**2016-09-16**

1609.05137 | math.CO

The switching model is a Markov chain approach to sample graphs with fixed
degree sequence uniformly… show more