tcs math – some mathematics of theoretical computer science

May 14, 2008

The Cheeger-Alon-Milman inequality

Filed under: Math — Tags: , , — James Lee @ 2:37 am

Recently, Luca posted on Cheeger’s inequality. Whenever I try to reconstruct the proof, I start with the coarea formula and then play around with Cauchy-Schwarz (essentially the way that Cheeger proved it). The proof below turned out to be a bit more complicated than I thought. Oh well…

Let G = (V,E) be a graph with maximum degree d_{\max} and n = |V|. Let’s work directly with the sparsity \displaystyle \alpha_G = \min_{S \subseteq V} \frac{e(S,\bar S)}{|S| |\bar S|} which is a bit nicer. Notice that \alpha_G n is within factor 2 of the Cheeger constant h_G. We start with a very natural lemma:

Coarea lemma: For any f : V \to \mathbb R, we have \sum_{ij \in E} |f(i)-f(j)| \geq \alpha_G \sum_{i,j \in V} |f(i)-f(j)|.

Proof: Let V_r = \{ i : f(i) \leq r \}, then we can write \sum_{ij \in E} |f(i)-f(j)| as the integral

\displaystyle \int_{-\infty}^{\infty} e(V_r, \bar V_r) dr \geq \alpha_G  \int_{-\infty}^{\infty} |V_r| |\bar V_r|dr = \alpha_G \sum_{i,j \in V} |f(i)-f(j)|

Now a bit of spectral graph theory: L = D - A is the Laplacian of G, where D is the diagonal degree matrix and A is the adjacency matrix. The first eigenvalue is \lambda_1 = 0 and the first eigenvector is (1,1,\ldots,1). If \phi : V \to \mathbb R is the second eigenvector, then the second eigenvalue can be written

\displaystyle \lambda_2 = \frac{\sum_{ij \in E} |\phi(i)-\phi(j)|^2}{\sum_{i \in V} \phi(i)^2}  \quad(1)

Given (1), it is natural to apply the coarea formula with f(i) = \phi(i)^2 and then play around.

Theorem: \displaystyle \lambda_2 \geq \frac{\alpha_G^2 n^2}{32 d_{\max}}

Proof: Unfortunately, if we try f(i) = \phi(i)^2, it doesn’t quite work (think of the case when \phi takes some value v and -v equally often). Instead, let’s eliminate this case by setting \phi_0(i) = \max(m,\phi(i)), where m = \mathrm{med}(\phi). Now applying the coarea lemma with f(i) = \phi_0(i)^2 yields:

\displaystyle \alpha_G \sum_{i,j \in V} |\phi_0(i)^2-\phi_0(j)^2| \leq \sum_{ij \in E} |\phi_0(i)^2-\phi_0(j)^2|

\displaystyle = \sum_{ij \in E} |\phi_0(i)+\phi_0(j)||\phi_0(i)-\phi_0(j)|  \leq \sqrt{\sum_{ij \in E} [\phi_0(i)+\phi_0(j)]^2} \sqrt{\sum_{ij \in E} |\phi_0(i)-\phi_0(j)|^2}

\displaystyle \leq \sqrt{2 d_{\max}}  \sqrt{n m^2 + \sum_{i \in V} \phi(i)^2} \sqrt{\sum_{ij \in E} |\phi(i)-\phi(j)|^2}\quad\quad (2)

Notice that the same inequality holds for \phi_1(i) = \min(m, \phi(i)). Also, observe that

\displaystyle \sum_{i,j \in V} |\phi_0(i)^2-\phi_0(j)^2| + |\phi_1(i)^2-\phi_1(j)^2|

\displaystyle \geq \frac{n}{2} \sum_{i : \phi(i) \geq m} [\phi(i)-m]^2 + \frac{n}{2} \sum_{i : \phi(i) \leq m} [\phi(i)-m]^2

\displaystyle = \frac{n}{2} \sum_{i \in V} [\phi(i)-m]^2 = \frac{n}{2} \left[n m^2 +\sum_{i \in V} \phi(i)^2\right],

where in the final line we have used the fact that \sum_{i \in V} \phi(i) = 0 since \phi is orthogonal to the first eigenvector.

So we can assume that \displaystyle \sum_{i,j \in V} |\phi_0(i)-\phi_0(j)|^2 \geq \frac{n}{4} \left[n m^2 +\sum_{i \in V} \phi(i)^2\right]. Plugging this into (2), rearranging, and using (1) yields the claim.

About these ads

2 Comments »

  1. [...] group in terms of on . But on a small, connected graph cannot be too close to zero by the discrete Cheeger inequality. In this way, we arrive at a contradiction if the image of the action is too small. Theorem 2 [...]

    Pingback by Eigenvalue multiplicity and growth of groups « tcs math - some mathematics of theoretical computer science — June 15, 2008 @ 9:25 am

  2. [...] For the proof, I’ll refer to Theorem 4 in Alon-Klartag.  Note that the proof for the Dirichlet version is even simpler than for the “standard” (Neumann) eigenvalues—it’s just a straightforward combination of Cauchy-Schwarz and the coarea formula. [...]

    Pingback by Lecture 2: Spectral partitioning and near-optimal foams « tcs math - some mathematics of theoretical computer science — September 26, 2008 @ 2:12 am


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Shocking Blue Green Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 64 other followers

%d bloggers like this: