In which we prove an analog of Cheeger’s inequalities for the largest Laplacian eigenvalue and we show how to use it to develop a spectral approximation algorithm for Max Cut.
1. Cheeger-type Inequalities for
Let be an undirected graph (not necessarily regular), its diagonal matrix of degrees, its adjacency matrix, its normalized Laplacian matrix, and be the eigenvalues of , counted with multiplicities and listed in non-decreasing order.
In Handout 2, we proved that if and only if has at least connected component and if and only if there is a connected component of (possibly, all of ) that is bipartite.
A special case of the former fact is that if and only if the graph is disconnected, and the Cheeger inequalities give a “robust” version of this fact, showing that can be small if and only if the expansion of the graph is small. In these notes we will see a robust version of the latter fact; we will identify a combinatorial parameter that is zero if and only if the graph has a bipartite connected component, and it is small if and only if the graph is “close” (in an appropriate sense) to having a bipartite connected components, and we will show that this parameter is small if and only if is small.
We will study the following combinatorial problem, which formalizes the task of finding an “almost bipartite connected component:” we are looking for a non-empty subset of vertices (we allow ) and a bipartition of such that there is a small number of “violating edges” compared to the number of edges incident on , where an edge is violating if it is in the cut , if it has both endpoints in , or if it has both endpoints in . (Note that if there are no violating edges, then is a bipartite connected component of .)
It will be convenient to package the information about as a vector , where the non-zero coordinates correspond to , and the partition of is given by the positive versus negative coordinates. We define the “bipartiteness ratio” of as
Note that in the numerator we have the number of violating edges, with edges contained in or in counted with a weight of 2, and edges from to counted with a weight of 1. In the denominator we have the sum of the degrees of the vertices of (also called the volume of , and written ) which is, up to a factor of 2, the number of edges incident on .
(Other definitions would have been reasonable, for example in the numerator we could just count the number of violating edges without weights, or we could have the expression . Those choices would give similar bounds to the ones we will prove, with different multiplicative constants.)
We define the bipartiteness ratio of as
We will prove the following analog of Cheeger’s inequalities: