While the Size of Subgraphs Grows
|Affiliation:||University of Waterloo|
|Room:||Mathematics and Computer Building (MC) 5136B|
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.
200 University Avenue West
Waterloo, ON N2L 3G1