# 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

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