*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.)

We define the sparsest cut of a graph as

Clearly we have

so we need to prove . We will do so by showing that is a *relaxation* of , that is, the computation of can be seen as an optimization problem that is identical to , except that we optimize over a bigger range of feasible solutions. To get started, we need to think about eigenvalues as solutions to optimization problems. This comes from characterizing eigenvalues via *Rayleigh quotients*. For our purposes (in which is the adjacency matrix of a -regular graph) we shall use the following simple identity

To prove the identity, take any vector orthogonal to (and hence to ), and write it in the orthonormal basis as

then the quotient in (2) is

and the quotient is equal to when .

The next step is to consider, for a vector , the quadratic form

which (up to normalization) measures the expected value of the quantity for a random edge , that is, how much the value of changes along edges. Since is the adjacency matrix of a -regular graph, we have

and so, combined with equation (2), we have

We are almost done with our manipulations. In the same spirit as Equation (4) we have

where is the matrix with a 1 in every entry. If , then

is the all-zero vector, and so we have

Finally, we observe that the quotient in (7) does not change if one adds the same constant to each coordinate of , and for every vector there is a contant (the average of the entries of ) such that is orthogonal to . This means that the requirement to optimize over vectors orthogonal to can be removed from (7) with no loss of generality. Hence,

Compare now Equation to the following way to look at sparsest cut, which is clearly equivalent to the standard definition

where the last equality comes from the fact that the absolute value of the difference of two boolean values is a boolean value, and hence equal to its square.

So we have found the *reason* why . Both and are the solution of a minimization problem, the cost function is the same in the two problems, but in the case of we are allowed to optimize over all of , while in the case of we restrict ourselves to .

In computer science, we very often see cases of intractable minimization combinatorial problems that can be relaxed to continuous optimization problems which can then be optimally solved, and the optimal solution of the relaxation gives a lower bound to the minimum of the combinatorial problem. When our continuous relaxation is a *linear program*, we have a theory of duality that gives us a *maximization* continuous dual problem such that the cost of any solution to the dual problem gives a lower bound to the optimum of the primal linear problem, and hence a lower bound to the minimum of the combinatorial problem.

Although it is not clear from the formulations given so far, it is possible to cast the computation of as the optimum of a *semidefinite programming* relaxation of sparsest cut; such a relaxation admits a *semidefinite dual*, and so any solution that is feasible for that semidefinite dual provides a lower bound to edge expansion. (And this fact can be checked very simply, with no reference to eigenvalues and eigenvectors, although there is in general no easier way to construct semidefinite dual feasible solutions than to use a system of eigenvectors.) This will be the subject of the next post.

## 4 comments

Comments feed for this article

May 1, 2008 at 7:06 am

Eigen1. How does all this tie in with Arora-Rao-Vazirani? Can one motivate ARV naturally from the discussion above?

2. Could you talk about the relationship (if any) between MAXCUT and spectral stuff?

Thanks.

May 3, 2008 at 11:41 am

lucaI cannot teach him. The boy has no patience.

June 1, 2008 at 11:32 am

toplisthi. super blog. thanks. toplist, site ekle

October 25, 2008 at 2:26 pm

youtubegirtesekkür ederim