3:00 p.m., Wednesday (January 23, 2008)
WMAX 110 (PIMS)
University of Toronto
Local limits of graphs
Abstract: There has been much recent progress in describing the structure of
general dense graphs and their limits, in the spirit of the Szemeredy
regularity lemma. I will present a new parallel theory for sparse graphs
(with bounded degrees). The limits are probability measures on infinite
graphs, and are the answer to the following question: What can the
neighbourhood of a random vertex in a finite graph look like?
I will present a characterization of the ergodic measures, an analogue
of the Szemeredi regularity lemma for sparse graphs and an application
of the theory: An Extension of a theorem of Benjamini and Schramm on
recurrence of limits planar graph limits to limits of graphs with an
excluded minor. No background is assumed.
Refreshments will be served at 2:45 p.m. (PIMS Lounge).