Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.

A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ λ2 ≥ ... λn ≥ -k. According to the most widespread definition, the graph is considered to be a good expander if λ2 is small. Random k-regular graphs (henceforth "random graphs") tend to be good expanders, and expanders have some of the important properties of random graphs, such as good connectivity.

However, there are many situations in which we would also like λn to be small in size. For example, the expander mixing lemma states that the number of edges connecting two subsets of the nodes in an "expander" is roughly what you'd expect in a random graph, but here "expander" means that λ ≔ max(|λ2|,|λn|) is small. Terry Tao, among others, has used the term "two-sided expander" to differentiate these graphs from the usual "one-sided expanders" of which they are a subset.


It is known that for any sequence of graphs with n increasing, lim inf λ ≥ 2√(k-1); and in fact λ converges almost-surely to this value for random graphs on n nodes.

My question concerns the "largest" (in terms of n) graph(s) for which λ ≤ x, given some x < 2√(k-1). How might we find these graphs, or at least constrain them (e.g. by finding a feasible range for n), possibly to a set which could be searched by computer? If the general problem is too difficult, what about the case k = 3, x = 2?

Edited the definitions in the first half and added some explanation, per comments on Igor Rivin's answer.

share|improve this question

1 Answer 1

I am not sure I understand the question. Usually an expander is a graph with a large spectral gap (in your language, a large $\lambda_1 - \lambda_2,$ though usually people look at graph laplacians, in which case you just want to maximize the smallest nonzero eigenvalue of the graph laplacian. The best expanders are Ramanujan graphs (google them), they hit the $2\sqrt{k-1}$ bound on the nose. Your definition ($\lambda_2 - \lambda_n$) is a bit puzzling...

share|improve this answer
    
Sorry, perhaps my question is poorly typeset. There's a comma in the definition of λ; it should read max(λ2,-λn) i.e. the largest of the two eigenvalues in absolute value. Perhaps max(|λ2|,|λn|) would have been clearer. –  Robin Saunders Aug 25 '13 at 1:54
    
Just in case there's still any confusion: since λ1 is equal to k and hence fixed, a large spectral gap is equivalent to a small λ2. Such graphs are sometimes called one-sided expanders, to contrast them with two-sided expanders where both λ2 and -λn are small. For simplicity, I write λ simply to denote the maximum of λ2 and -λn. –  Robin Saunders Aug 25 '13 at 1:55
3  
@RobinSaunders I would suggest you incorporate your comments into the question: I know a fair bit about expanders, but this is the first I have heard of "two-sided expanders". –  Igor Rivin Aug 25 '13 at 2:41
    
Thanks. Because I'm not familiar with the literature, it didn't occur to me that this would be a point of confusion. Done. –  Robin Saunders Aug 25 '13 at 15:38
    
If I recall correctly a lecture I've heard from Alex Lubotzky a few years ago, in his construction of explicit Ramanujan graphs, there's a difference between PGL and PSL (depending on whether some prime splits or not), one of them gives you two-sided expander (as the Hecke operators will move you between the sides). It might be worthwhile to look into this point. I've actually discussed a related issue with Sarnak a few days ago... –  Asaf Jan 22 at 19:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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