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 Colloquium - Mikhail IsaevExport this event to calendar

Friday, May 24, 2019 — 3:30 PM EDT

Title: The sandwich conjecture of random regular graphs and more

Speaker: Mikhail Isaev
Affiliation: Monash University
Room: MC 5501

Abstract:

The sandwich conjecture formulated in [Kim, Vu, Advances in Math., 2004] states that if d >> log n, then the random d-regular graph on n vertices R(n, d) can asymptotically almost surely be ”sandwiched” between G(n, p1) and G(n, p2) where probabilities p1 and p2 are both (1 + o(1))d/n. They proved this conjecture for the range log n << d < n1/3−o(1) with a defect in one side of sandwiching: a few edges from each vertex should be deleted from R(n, d) to guarantee the containment in G(n, p2). Recently, their one-sided containment result G(n, p1) ⊂ R(n, d) was extended by Dudek, Frieze, Rucinski and Sileikis to any log n << d = o(n).
We prove the sandwich conjecture (with perfect containments on both sides) for all values of d > n/ log n. For smaller values of d we establish non-tight containment R(n, d) ⊂ G(n, p) with p = ε(d/n) log n (for any constant ε > 0).
This is joint work with P. Gao and B.D. McKay

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
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. 2021 (71)
    1. August (2)
    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)