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