<p>Regarding the last eigenvalue:</p>

<p>The last eigenvalue $\lambda_n$ measures (roughly) how close is the graph to be bipartite. For example, $\lambda_n = -d$ if and only if the graph is bipartite (this is a fairly easy exercise). You can read more about it in Luca Trevisan's blog:</p>

<p><a href="http://lucatrevisan.wordpress.com/2008/06/13/max-cut-and-the-smallest-eigenvalue/">http://lucatrevisan.wordpress.com/2008/06/13/max-cut-and-the-smallest-eigenvalue/</a></p>

<p><a href="http://lucatrevisan.wordpress.com/2008/09/23/max-cut-gain-and-the-smallest-eigenvalue/">http://lucatrevisan.wordpress.com/2008/09/23/max-cut-gain-and-the-smallest-eigenvalue/</a></p>

CC BY-SA 3.0
2013-04-30T19:09:46.253Z
Thanks a lot for the answer. I will look through the link that you shared.
NAg
CC BY-SA 3.0
2013-04-29T03:33:59.653Z
2013-04-29T03:33:59.653Z
Or Meir
<p>Note : All eigenvalues that I would referring to below would of the adjacency matrix of the graph</p>

<p>My question arises from having read about Expander Graphs from a few different sources. The most common definition of Expander Graphs that have seen is in terms of the spectral gap which is $d - \lambda _2$ where $\lambda _2$ is the second highest eigenvalue. However certain sources also like to define expansion in terms of $\lambda$ which is the second highest eigenvalue in absolute value. Now I am slightly confused about what is a better definition and why these two values are so mixed in literature ? </p>

<p>For instance Cheeger's inequalities are defined in terms of $\lambda _2$ and the Expander Mixing Lemma is defined is terms of $\lambda$ (I am not sure if there exist versions of each in terms of the other quantity). Also I have seen versions of the Alon-Bopanna bound in terms of both $\lambda$ and $\lambda _2$. </p>

<p>I guess my question is that is there a fundamental connection between these two quantities and is one more natural than the other to be used to define expansion ?</p>

<p>Also is there something fundamental that $\lambda _n$ (by $\lambda _n$ I mean the smallest eigenvalue) represent ?   </p>

<p>I am not sure if I have been able to express my confusion clearly but I am sure I am missing something fundamental in my understanding.</p>

<p>Thanks</p>

CC BY-SA 3.0
2013-04-29T03:41:57.443Z
It might be that some of the proofs need an upper bound on all the eigenvalues other than the maximal ones, in which case the relevant quantity is $\lambda_2$, and other proofs need an upper bound on the *absolute value* of all eigenvalues other than the maximal one, in which case the relevant quantity is $\max(\lambda_2,-\lambda_n)$. The latter happens, for example, when you use Cauchy-Schwartz. Perhaps it is the case that for a random graph (not a random bipartite graph!), $\lambda_n$ is small in magnitude compared to $\lambda_2$.
Yuval Filmus
<spectral-graph-theory><expanders>
Second eigenvalue and the last eigenvalue
NAg
# Second eigenvalue and the last eigenvalue

(Asked by: username_0 on 2013-04-29)

Note : All eigenvalues that I would referring to below would of the adjacency matrix of the graph

My question arises from having read about Expander Graphs from a few different sources. The most common definition of Expander Graphs that have seen is in terms of the spectral gap which is $d - \lambda \_2$ where $\lambda \_2$ is the second highest eigenvalue. However certain sources also like to define expansion in terms of $\lambda$ which is the second highest eigenvalue in absolute value. Now I am slightly confused about what is a better definition and why these two values are so mixed in literature ?

For instance Cheeger's inequalities are defined in terms of $\lambda \_2$ and the Expander Mixing Lemma is defined is terms of $\lambda$ (I am not sure if there exist versions of each in terms of the other quantity). Also I have seen versions of the Alon-Bopanna bound in terms of both $\lambda$ and $\lambda \_2$.

I guess my question is that is there a fundamental connection between these two quantities and is one more natural than the other to be used to define expansion ?

Also is there something fundamental that $\lambda \_n$ (by $\lambda \_n$ I mean the smallest eigenvalue) represent ?

I am not sure if I have been able to express my confusion clearly but I am sure I am missing something fundamental in my understanding.

Thanks

**Tags:** spectral-graph-theory, expanders

> **Comments:**
> **username_1**: It might be that some of the proofs need an upper bound on all the eigenvalues other than the maximal ones, in which case the relevant quantity is $\lambda_2$, and other proofs need an upper bound on the *absolute value* of all eigenvalues other than the maximal one, in which case the relevant quantity is $\max(\lambda_2,-\lambda_n)$. The latter happens, for example, when you use Cauchy-Schwartz. Perhaps it is the case that for a random graph (not a random bipartite graph!), $\lambda_n$ is small in magnitude compared to $\lambda_2$.  

---

## 1 answers

### Answer by username_2 on 2013-04-29. Score: 5

Regarding the last eigenvalue:

The last eigenvalue $\lambda\_n$ measures (roughly) how close is the graph to be bipartite. For example, $\lambda\_n = -d$ if and only if the graph is bipartite (this is a fairly easy exercise). You can read more about it in Luca Trevisan's blog:

<http://lucatrevisan.wordpress.com/2008/06/13/max-cut-and-the-smallest-eigenvalue/>

<http://lucatrevisan.wordpress.com/2008/09/23/max-cut-gain-and-the-smallest-eigenvalue/>

> **Comments:**
> **username_0**: Thanks a lot for the answer. I will look through the link that you shared.  

---

