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.

Graph theory seminar - Nick WormaldExport this event to calendar

Thursday, October 9, 2014 — 4:00 PM EDT

On the Diameter and Longest Paths in Random Apollonian Networks

Speaker: Jim Geelen
Affiliation: University of Waterloo
Room: Mathematics and Computer Building (MC) 6486

Abstract: 

Start with a triangle embedded in the plane. In each step, choose a bounded face uniformly at random, add a vertex inside that face and join it to the vertices of the face. After n-3 steps, we obtain a random triangulated plane graph with n vertices, which is called a random Apollonian network. Asymptotically almost surely, the diameter of the resulting network is is asymptotic to c log n, where c ~ 1.668, and the longest path length is at most n^δ for some δ<1.

The latter result refutes a conjecture of Frieze and Tsourakakis, and confirms a conjecture of Cooper and Frieze. For its proof, we bound the size of the largest regular (r-ary) subtrees of the random recursive tree with t vertices.

Includes joint work with Andrea Collevecchio, Ehsan Ebrahimzadeh, Linda Farczadi, Pu Gao, Abbas Mehrabian, Cristiane M. Sato, Jonathan Zung.

Location 
MC - Mathematics & Computer Building
6486
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)