Spectral Graph Theory (XII)
by Hamid Mokhtar
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.