The problem of efficiently sampling from a set of(undirected) graphs with a given degree sequence has many applications. One approach to this problem uses a simple Markov chain, which we call the switch chain, to perform the sampling. The switch chain is known to be rapidly mixing for regular degree sequences. We prove that the switch chain is rapidly mixing for any degree sequence with minimum degree at least 1 and with maximum degree @math which satisfies @math , where @math is the sum of the degrees. The mixing time bound obtained is only an order of @math larger than that established in the regular case, where @math is the number of vertices.
Finally we note that Barvinok and Hartigan @cite_15 showed that the adjacency matrix of a random element of @math is close'' to a certain maximum entropy matrix'', when the degree sequence is . The definition of tame depends on the maximum entropy matrix, but a sufficient condition is that @math and @math for some constants @math . Some degree sequences satisfying this latter condition are stable sequences, and many of these degree sequences also satisfy the condition of Theorem . It would be interesting to explore further the connections between stable degree sequences, tame degree sequences and the mixing rate of the switch Markov chain.
@cite_15
2004542856
We consider the set of all graphs on n labeled vertices with prescribed degrees D = (d1,…,dn). For a wide class of tame degree sequences D we obtain a computationally efficient asymptotic formula approximating the number of graphs within a relative error which approaches 0 as n grows. As a corollary, we prove that the structure of a random graph with a given tame degree sequence D is well described by a certain maximum entropy matrix computed from D. We also establish an asymptotic formula for the number of bipartite graphs with prescribed degrees of vertices, or, equivalently, for the number of 0-1 matrices with prescribed row and column sums. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013