3:00 p.m., Wednesday (January 23, 2008)


Omer Angel
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).

Copyright © 2008 UBC Mathematics Department