University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Nick WormaldExport this event to calendar

Friday, October 10, 2014 — 3:30 PM EDT

Enumeration of Graphs with a Heavy-tailed Degree Sequence

Speaker: Nick Wormald
Affiliation: Monash University
Room: Mathematics (M3) 3103

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.

Location 
M3 - Mathematics 3
3103
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2021 (74)
    1. August (5)
    2. July (10)
    3. June (12)
    4. May (7)
    5. April (9)
    6. March (13)
    7. February (8)
    8. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)