## Lecture 6: Cheeger-Alon-Milman Inequality

**1**. We showed that Gap-Max-3SAT is NP-Hard for some constants using -edge expanders ( is a constant). The proof relies on the fact that such an expander can be constructed in polynomial time. In the last lecture, we only proved that such expanders exist for all sufficiently large , but we have not discussed how to construct expanders in polynomial time yet. Efficient constructions of good expanders will be discussed probably next week.

**2**. We proved half of the so-called Cheeger-Alon-Milman inequality, which states that

for any -regular graph . Here, is the second largest eigenvalue and is the edge-isoperimetric number of the graph. We showed only that . Briefly, the proof went as follows.

First, we “symmetrize” .

Define the sparsity of to be

Then, we just showed that . It remains to show that . To do so, we turn the expression for into a more algebraic form. Imagine assigning a value of 1 to each vertex in and 0 to each vertex in , we get a vector . It is not difficult to see that

So, is the objective value of a certain optimization problem over zero-one vectors in . If we relax the zero-one condition, we get a lower bound for . Specifically,

Now, subtract (or add) the same amount from (to) each will not change the min. Hence, we can replace each vector by where . This way, , or simply . Consequently,

Now, let be the adjacency matrix of , then it can be verified straightforwardly that

Moreover, if , then . Consequently,

For a more elaborate discussion on Cheeger-Alon-Milman inequality, see a nice series of posts by Luca Trevisan on the topic.

leave a comment