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 - Christian BorgsExport this event to calendar

Friday, November 16, 2012 — 3:30 PM to 4:30 PM EST

Convergence of sparse graphs as a problem at the intersection of graph theory, statistical physics and probility

Speaker: Christan Borgs
Affiliation: Microsoft Research New England
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Many real-world graphs are large and growing. This naturally raises the question of a suitable concept of graph convergence. For graphs with average degree proportional to the number of vertices (dense graphs), this question is by now quite well-studied. But real world graphs tend to be sparse, in the sense that the average or even the maximal degree is bounded by some reasonably small constant. In this talk, I study several notions of convergence for graphs of bounded degree and show that, in contrast to dense graphs, where various a priori different notions of convergence are equivalent, the corresponding notions are not equivalent for sparse graphs. I then describe a notion of convergence formulated in terms of a large deviation principle which implies all previous notions of convergence. 

No prior knowledge of graph convergence or large deviation theory is needed.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
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
1
2
  1. 2021 (85)
    1. October (1)
    2. September (8)
    3. August (7)
    4. July (10)
    5. June (12)
    6. May (7)
    7. April (9)
    8. March (13)
    9. February (8)
    10. 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)