1
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – Yuval Filmus
    Apr 29, 2013 at 3:41

1 Answer 1

Reset to default
5
$\begingroup$

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/

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot for the answer. I will look through the link that you shared. $\endgroup$
    – NAg
    Apr 30, 2013 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.