Cheeger-Type Inequalities using Reweighted Eigenvalues - Lap Chi Lau

Title: Cheeger-Type Inequalities using Reweighted Eigenvalues

Abstract: Cheeger's inequality is a fundamental result in spectral graph theory connecting the edge conductance of an undirected graph to the second eigenvalue of its Laplacian matrix.  In this talk, we will present a unifying approach to prove Cheeger-type inequalities in more general settings using the concept of reweighted eigenvalues.  This provides a new spectral theory for vertex expansion, for directed graphs, and for hypergraphs, that is much closer to the spectral theory for undirected graphs that were previously known.  An interesting consequence is a characterization of the fastest mixing time of a directed graph by its vertex expansion.

Joint work with Tsz Chiu Kwok, Kam Chuen Tung, and Robert Wang.