# Second eigenvalue and the last eigenvalue

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

• 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 Apr 29 '13 at 3:41

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: