Counting loopy graphs with given degrees

Abstract

Let d=(d_1,d_2,..., d_n) be a vector of non-negative integers. We study the number of symmetric 0-1 matrices whose row sum vector equals d. While previous work has focussed on the case of zero diagonal, we allow diagonal entries to equal 1. When forming the row sum, each diagonal entry is multiplied by a factor of D, where D is 1 or 2. The case D=1 corresponds to enumeration by the usual row sum of matrices. The case D=2 corresponds to enumeration by degree sequence of undirected graphs with loops but no repeated edges, due to the convention that a loop contributes 2 to the degree of its incident vertex. We obtain asymptotically precise formulae for the number of matrices in the sparse range (where, roughly, the maximum row sum is o(n^{1/2})), and in the dense range (where, roughly, the average row sum is proportional to n and the row sums do not vary greatly).

Fixed an obvious typo in Thm 1.5

References in corpus (4)

• Metric measure spaces with Riemannian Ricci curvature bounded from below
• Uniform convergence to equilibrium for granular media
• Transportation-information inequalities for Markov processes (II) : relations with other functional inequalities
• Unbiased Estimators for Entropy and Class Number

Cited by in corpus (6)

• Study of the cofactor conditions: conditions of supercompatibility between phases
• Search for direct top squark pair production in final states with one isolated lepton, jets, and missing transverse momentum in sqrt(s) = 7 TeV pp collisions using 4.7 fb-1 of ATLAS data
• Neuron-Glial Interactions
• Cross-calibration of Time-of-flight and Colour Cameras
• Effects of interplanetary shock inclinations on nightside auroral power intensity
• Influence of the Geomagnetic Field on the IACT detection technique for possible sites of CTA observatories