Enumeration of Graphs With A Heavy-Tailed Degree Sequence<br/><br/>

Monday, September 8, 2014 - 11:30am - 12:20pm
Keller 3-180
Nick Wormald (Monash University)
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.
MSC Code: