In which we dwell at great length on the “easy” part of Cheeger’s inequality.
The edge expansion of a graph , defined as
is a measure of how “well connected” is a graph. A graph has edge expansion at least if and only if, in order to disconnect a set of vertices from the rest of the graph, one must remove at least edges. In other words, the removal of edges from a graph of edge expansion must leave a connected component of size , where is the number of vertices.
As readers of in theory know, graphs of large edge expansion (expander graphs) have many applications, and in this post we are going to return to the question of how one certifies that a given graph has large edge expansion.
For simplicity, we shall only talk about regular graphs. In a previous post we mentioned that if is the adjacency matrix of a graph, there are numbers (the eigenvalues of ), not necessarily distinct, and an orthonormal basis of , such that for all
And if the graph is -regular, then , , and for all we have . Finally, the numbers and the vectors are computable in polynomial time. (This is all the linear algebra we will need.)
Given this setup, we have the lower bound
That is, the difference between largest and second largest eigenvalue gives a lower bound to the edge expansion of the graph.
Although (1) is very easy to prove, it is a remarkable result, in the sense that it gives a polynomial-time computable certificate of a “coNP” statement, namely, that for all cuts, at least a certain number of edges cross the cut. Since computing edge expansion is NP-complete, the inequality cannot always be tight. Eventually shall compare it with other methods to lower bound the edge expansion, and see that they are all special cases of the same general approach. To begin with, in this post we shall show that is an efficiently computable relaxation of the edge expansion problem. (Or, rather, of the closely related sparsest cut problem.) Continue reading