School Seminars and Colloquia

Spectral Graph Theory (XII)

Discrete Structures and Algorithms (Reading Group)

by Hamid Mokhtar


Institution: The University of Melbourne
Date: Wed 23rd May 2012
Time: 1:00 PM
Location: Room 107, Richard Berry Building

Abstract: We will discuss Chapter 4 of Chung's book, Spectral Graph Theory. We will define paths, routings and flows, and then use them to establish a lower bound for the Cheeger constant and lower bounds for the second smallest Laplace eigenvalue. Results of this kind can also be interpreted as lower bounds on the product of the `dilation' and `edge-congestion' of a symmetrical routing. We will also discuss eigenvalues and routings with small congestion.