The number of graphs and a random graph with a given degree sequence

Understand

We consider the set of all graphs on n labeled vertices with prescribed degrees D=(d_1, ..., d_n).

• For a wide class of tame degree sequences D we prove 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.