Show that the isoperimetric number $i(G)$ of $G$ satisfies $i(G) \le \mu/2$

77 Views Asked by At

That's the problem:

Let $G$ be a graph with a Laplacian eigenvalue $\mu > 0$ which has an eigenvector $v$ with entries in $\{−1,1\}$. Show that the isoperimetric number $i(G) $ of $G$ satisfies $i(G) \le \mu/2$. Deduce that $i(G) = \mu_2/2$.

For the first part, I know that the eigenvector is parallel to one of the axis, and $v$ is orthogonal to the other eigenvectors which have different eigenvalues than $\mu$. I also know:

$$\frac{\mu_2}{n} \leq \frac{e(A,V \backslash A)}{|A|(n−|A|)} \leq \frac{\mu_n}{n}$$

and by Cheeger's inequality:

$$\frac{\mu_2(G)}{2} \leq i(G) \leq \sqrt{2\Delta \mu_2}$$

It is not obvious to me how to relate the eigenvalue $\mu$ being positive and his eigenvector being parallel to an axis, to the properties of $G$ in general and ending up determining the results above.

I would appreciate any good intuition behind it. Thanks!

1

There are 1 best solutions below

0
On

I believe you are supposed to assume (or prove) that the $\mu$ in the statement is indeed the smallest non-zero eigenvalue $\mu_2$.

From there, you can prove the claim as follows:

First, we study $v$ to obtain some information about it. Let $S\subset \{1,\dots,n\}$ be the indices where $v$ is $1$. Using the known fact that $v$ is orthogonal to eigenvectors of different eigenvalue, we know that in particular $v\bot (1,1,\dots,1)$ because $v_1=(1,\dots,1)$ is an eigenvector of eigenvalue $\mu_1=0$. Since the entries of $v$ are $\pm 1$ this tells us that \begin{equation*} 0=v_1^Tv=\sum\limits_{i\in S}1 + \sum\limits_{i\notin S}-1 = |S| - (n-|S|) \Longrightarrow |S|=\frac{n}{2}. \end{equation*}

In other words, there are as many $1$'s as $-1$'s in $v$.

Secondly, Courant-Fischer and some analysis gives us that \begin{equation*} \mu_2 = \frac{v^TLv}{v^Tv} = \frac{1}{n}v^TLv = \sum\limits_{ij\in E(G)}\left(v(i)-v(j)\right)^2. \end{equation*}

But since $v\in \{-1, 1\}^n$ this squared difference can only take two values: $0$ or $2^2=(-2)^2=4$. The edges $ij\in E(G)$ in which $(v(i)-v(j))^2=4$ are exactly the edges with one endpoint in $S$ and one endpoint in $V\backslash S$. Therefore we have \begin{equation*} \sum\limits_{ij\in E(G)}\left(v(i)-v(j)\right)^2=4e(S, V\backslash S). \end{equation*}

By the definition of $i(G)$ and using the fact that $|S|=n/2$ we can bound $e(S, V\backslash S)$. \begin{equation*} i(G)=\min\left\{\frac{e(S, V\backslash S)}{|S|} : 0<|S|\leq n/2\right\} \Longrightarrow e(S, V\backslash S) \geq |S|i(G) = \frac{n}{2}i(G) \end{equation*} and finally we have \begin{equation*} \mu_2 = \frac{1}{n} 4e(S, V\backslash S) \geq \frac{4}{n} |S| i(G) = \frac{4}{n} \frac{n}{2} i(G) = 2i(G). \end{equation*}

I hope it was helpful!