Cheeger-Type Inequalities using Reweighted Eigenvalues - Lap Chi Lau

Monday, February 6, 2023 11:30 am - 11:30 am EST (GMT -05:00)

Title: Cheeger-Type Inequalities using Reweighted Eigenvalues

Speaker: Lap Chi Lau
Institution: University of Waterloo
Location: Contact Sabrina Lato for zoom link

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.