Videos

Enumeration of Graphs With A Heavy-Tailed Degree Sequence

Presenter
September 8, 2014
Keywords:
  • Enumeration, Graphs
MSC:
  • 05C30
Abstract
The number of graphs with a given degree sequence is still not known in any convenient form, even asymptotically, for moderately dense graphs. We obtain a formula that includes some heavy-tailed sequences in the sparse case (i.e. where the average degree is rather small). Our general result requires upper bounds on the k-th moment of the degree sequence, for a few small integers k. Special cases include the first asymptotic enumeration results applicable to degree sequences following a power law with parameter between 2 and 3, which is the realm of empirically observed real-world networks. Another special case extends a recent result of Janson. A previous result on sparse graphs applies to a wide range of degree sequences but requires maximum degree M to the power 1/3, where M is the number of edges. Our new result applies in some cases when the maximum degree is almost the 3/5 power of M. The basic method is, as usual, that of estimating a very small probability, of the event that the random configuration model gives a simple graph. This is joint work with Jane Gao.