Higher Order Cheeger Inequalities


Jenish Mehta


California Institute of Technology
Department of Computer Science
1200 E Calfornia Blvd|
Pasadena, CA 91125
United States of America


Friday, 12 August 2016, 16:00 to 17:30


  • A-201 (STCS Seminar Room)


Cheeger inequalities in spectral graph theory help to comment on the approximate connectivity or expansion of a graph (a combinatorial property) from the eigenvalues of the adjacency matrix of the graph (an algebraic property). More specifically, it says that the expansion of a graph can be tightly bound by the second largest eigenvalue of the graph. The Cheeger inequalities were generalized by Lee-Gharan-Trevisan so that the k-way expansion of a graph can be approximated by the k largest eigenvalues of the adjacency matrix.

In this talk, i will present the higher order cheeger inequality, which roughly says, that the first k eigenvalues of the laplacian of a graph are close to 0 if and only if we can find k approximately disjoint subsets in the graph. I will start with the basics and show the inequality.

Paper: https://arxiv.org/abs/1111.1055