Higher Order Cheeger Inequalities

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