*In which we prove the difficult direction of Cheeger’s inequality.*

As in the past lectures, consider an undirected -regular graph , call its adjacency matrix, and its scaled adjacency matrix. Let be the eigenvalues of , with multiplicities, in non-increasing order. We have been studying the *edge expansion* of a graph, which is the minimum of over all non-trivial cuts of the vertex set (a cut is trivial if or ), where the expansion of a cut is

We have also been studying the (uniform) *sparsest cut* problem, which is the problem of finding the non-trivial cut that minimizes , where the sparsisty of a cut is

We are proving Cheeger’s inequalities:

and we established the left-hand side inequality in the previous lecture, showing that the quantity can be seen as the optimum of a continuous relaxation of , so that , and follows by the definition.

Today we prove the more difficult, and interesting, direction. The proof will be constructive and algorithmic. The proof can be seen as an analysis of the following algorithm.

Algorithm: *SpectralPartitioning*

- Input: graph and vector
- Sort the vertices of in non-decreasing order of values of entries in , that is let where
- Let be such that is minimal
- Output

We note that the algorithm can be implemented to run in time , assuming arithmetic operations and comparisons take constant time, because once we have computed it only takes time to compute .

We have the following analysis of the quality of the solution:

Lemma 1 (Analysis of Spectral Partitioning)Let be a d-regular graph, be a vector such that , let be the normalized adjacency matrix of , defineand let be the output of algorithm

SpectralPartitioningon input and . Then

Remark 1If we apply the lemma to the case in which is an eigenvector of , then , and so we have

which is the difficult direction of Cheeger’s inequalities.

Remark 2If we run the SpectralPartitioning algorithm with the eigenvector of the second eigenvalue , we find a set whose expansion isEven though this doesn’t give a constant-factor approximation to the edge expansion, it gives a very efficient, and non-trivial, approximation.

As we will see in a later lecture, there is a nearly linear time algorithm that finds a vector for which the expression in the lemma is very close to , so, overall, for any graph we can find a cut of expansion in nearly linear time.