How to find or constrain “particularly good” (two-sided) spectral expanders?

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.

• Note expander are usually defined to be certain families of graphs. A single graph being an expander, without further qualification, does not make too much sense. – Kimball May 18 '15 at 13:36
• Right - which is why, in my question, I specifically asked about "the largest (in terms of n) graph(s) for which λ ≤ x, given some x < 2√(k-1)" where n is the number of vertices, k is the degree, λ is the largest absolute value of a non-trivial eigenvalue of the adjacency matrix. – Robin Saunders May 19 '15 at 14:21

1 Answer

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...

• 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
• @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
• 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 '14 at 19:31
• @Asaf, I heard Lubotzky speak about 4 weeks ago and he definitely said psl2 gives 2-sided expanders. – Benjamin Steinberg Oct 20 '14 at 2:19
• It's not true that Ramanujan graphs hit the asymptotic bound on the nose, but they can beat bound. – Kimball May 18 '15 at 13:38