| Start Date: | 10/6/2014 | Start Time: | 3:00 PM |
| End Date: | 10/6/2014 | End Time: | 4:00 PM |
|
Event Description
Nick Wormald, professor of mathematics, Monash University, Australia
Abstract: When a network grows randomly, the point at which it achieves a given property can often be pinpointed in advance with high probability. In their early work on random graphs in the late 50s, Erdos and Renyi considered the threshold of appearance of a giant component, and of various other subgraphs.
The models of random graphs introduced at that time have received much attention since then, and have found many applications, particularly in
computer science. Many interesting results can be stated in terms of the random graph process. In this, the random graph grows in time by the addition of
random edges, making the graph ever denser as time goes on. The threshold of appearance of a given subgraph H can be defined as the time at which the random graph process contains a copy of H with probability at least 1/2.
Kahn and Kalai made a simple-sounding but deep conjecture relating this threshold to another one: the threshold of expectation for a subgraph H
is the time at which the expected number of copies of H in the random graph process exceeds 1. One very special case of this conjecture gained some
notoriety as the comb conjecture, made about 15 years ago by Kahn.
Random regular graphs are a different but commonly used model of random graphs with low density. This model enters somewhat surprisingly into a solution of the comb conjecture, recently obtained jointly with Jeff Kahn and Eyal Lubetzky. In this talk I will give an exposition of results on random graphs and random regular graphs, with the proof of the comb conjecture as a focus. |
|
Location:
Korman Center, Room 245, 15 South 33rd Street, Philadelphia, PA 19104 |
|
