*In which we state an analog of Cheeger’s inequalities for the -th smallest Laplacian eigenvalue, and we discuss the connection between this result and the analysis of spectral partitioning algorithms*

**1. Review **

Let be a -regular undirected graph, its normalized Laplacian, be the Laplacian eigenvalues, and be the order- expansion of .

We want to prove

We will prove the somewhat stronger result that, given orthonormal vectors , we can find disjointly supported vectors such that, for every ,

In order to do that, we define the mapping

of vertices to and the normalized distance

between vertices, and we are going to prove the following two lemmas.

Lemma 1 (Localization)Given sets such that, for every , and,for every in different sets , we can construct disjointly supported vectors such that for every , we have

Lemma 2 (Well-Separated Sets)There are disjoint subsets of vertices such that

- For every ,
- For every and belonging to different sets,

Recall that, for a function the Rayleigh quotient of is defined as

and, by definition of , we have

**2. Some Preliminaries **

We will prove some simple properties of the embedding and of the distance function .

First, we observe that

Next, we prove the sense in which “spreads out” vertices across .

Lemma 3For every unit vector ,

*Proof:* Consider the matrix whose rows are the vectors and whose columns are the points . Then we have

where we used the fact that the rows of are orthogonal and so is the identity.

This means that, for every direction, the points correlate with that direction in the same way, regardless of the direction itself.

In the proof of the localization lemma, we will make use of the following inequality: for every two vectors ,

which is a consequence of Cauchy-Schwarz:

**3. Localization **

In this section we prove Lemma 1.

** 3.1. Proof Ideas **

The basic idea is that we would like to define the vectors as

The denominator of the Rayleigh quotient of such a vector is, by definition, at least , and we might hope to upper bound the numerator of the Rayleigh quotient of in terms of the numerator of the Rayleigh quotient of , which is .

Indeed, every edge with both endpoints outside of contributes zero to the numerator of the Rayleigh quotient of , and every edge with both endpoints in contributes

to the numerator of the Rayleigh quotient of , and the right-hand-side above is the contribution of the edge to the numerator of the Rayleigh quotient of .

So far, so good, but the problem comes from edges with one endpoint and one endpoint . Such an edge contributes to the Rayleigh quotient of and to the Rayleigh quotient of , and the former quantity could be much larger than the latter. If is large, however, cannot be much larger than , because of the following fact

*Proof:*

We can conclude that the only problem comes from edges such that , , and is small. To deal with such edges, we will modify the definition of , and use a “smoothed” version of the indicator function of instead of the actual indicator.

** 3.2. Proof **

If is a vertex and is a set of vertices, we define

For each , we define the following *smooth indicator function* of :

Notice that the functions are disjointly supported: there cannot be a vertex such that and for , otherwise we would have and , contradicting the well-separated condition on the sets .

We define the vectors as

The vectors are disjointly supported, and it remains to understand their Rayleigh quotient.

The denominator of the Rayleigh quotient of is

The contribution of an edge to the numerator is the square of

where we used the inequality

The numerator of the Rayleigh quotient of is thus

and this proves Lemma 1.

**4. Well-Separated Sets **

In this section we prove Lemma 2, which follows easily from the following result.

Lemma 5We can find disjoint sets of vertices such that

- For every , in different sets,
- For every set ,

We can derive Lemma 2 from Lemma 5 as follows. Let us call the quantity the *mass* of a set . Starting from the sets promised by Lemma 5 we run the following process: as long as there are two sets both of mass we merge them. Call the sets of mass obtained at the end of this process; in addition, there may be one more set of mass . Every set has mass . This means that the total mass of the sets is at most , which implies . Thus we have found sets of vertices, each of mass at least , and such that any two sets have separation .

Now we turn to the proof of Lemma 5. We are going to use the fact that, for every small cone in , the mass of vertices such that is in the cone is also small and, in particular, it can made at most . We will prove the Lemma by covering almost all the points using a collection of well-separated small cones.

We first formalize the above intuition about cones. If (for *r*egion) is a subset of the unit sphere in , then the diameter of is

and the *cone* generated by is the set of non-negative scalar multiples of elements of . The set of vertices covered by , denoted is the set of vertices such that is in the cone generated by or, equivalently,

If has small diameter, then has small mass.

Lemma 6For every subset of the unit sphere,

*Proof:* For every two unit vectors and , we have

For every vertex , call

Let be a vector in . Then we have

In particular, if , then the mass of is at most

Another observation is that, for every two subsets of the unit sphere,

Our approach will be to find disjoint subsets of the unit sphere, each of diameter at most , such that the total mass of the sets is at least and such that the separation between any two is at least .

To do this, we tile with axis-parallel cubes of side , which clearly have diameter at most , and, for every cube , we define its *core* to be a cube with the same center as and of side . Note two points in the core of two different cubes have distance at least . Let now be the intersections of the cube cores with the unit sphere. Since each is a subset of a core of a cube, it has diameter at most , and the distance between any two points in different regions is at least . We claim that there is a way to choose the location of the centers of the cubes so that .

Let us start by a fixed configuration of the cubes and then apply an axis-parallel random shift (by adding to each coordinate, a random real in the range . Then, for each fixed point in and, in particular, for each point , the probability that it falls in the core of a cube after the shift is at least , so the average mass of the vertices covered by the regions is at least , and there must exist a shift that is at least as good.

Typo in proof of lemma 3: should be “w^T X X^T w”

and then “X X^T is identity”

@Yu Zhao: thanks.

I would also like to thank Arnold Filtser, who sent me a lot of corrections for this lecture

Right after Lemma 5, in the paragraph showing the connection of Lemma 5 to Lemma 2, it states that “Every set has mass at most 1 + 1/4k. This means that the total mass of the sets is at most 1/2 + t (1 + 4k)”.

Given the context, I assume that this refers to sets A_1, …, A_t that come up after the merging procedure. Nonetheless the fact that every set has mass at most 1+1/4k is true only for sets T_1, …, T_m. In my understanding the mass of a set A_i can be larger that 1+1/4k since A_i may come up from the merging of several of the sets T_1, …, T_m.

What am I missing here?