  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.
