Friday, November 14, 2014 — 3:30 PM EST

While the Size of Subgraphs Grows

Speaker: Jane Gao
Affiliation: University of Waterloo
Room: Mathematics and Computer Building (MC) 5136B

Abstract:

Consider the random graph process starting from an empty graph on n vertices, with one random edge being placed in each step. For a given graph H, at which step of the process will H appear as a subgraph? For H with a fixed size, say a triangle, roughly speaking, this happens when the expected number of the copies of H becomes at least one. However, this is no longer true when H has a growing size as n, e.g. if H is a Hamilton cycle, due to a heavy correlation between the copies of H in the random graph.

Dealing with heavy correlations is a big challenge when studying large
subgraphs or structures in random objects. Such heavy correlations
sometimes result in surprising and anti-intuitive phenomena. I will
survey the literature on properties of large subgraphs in several random
graph models; particularly on their appearance thresholds and the
distributions of their counts. As a particular example, we will study
the distribution of the number of matchings of size t in G(n,p), when t
grows from one to n/2. We show that there is exactly one transition of
the limiting distribution as t grows, and we determine exactly when this
transition takes place. This talk contains joint work with Cris Sato.

Location 
MC - Mathematics & Computer Building
5136B
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 (92)
    1. October (5)
    2. September (12)
    3. August (6)
    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)