12
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kimball
    May 18, 2015 at 13:36
  • $\begingroup$ 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. $\endgroup$
    – Robin Saunders
    May 19, 2015 at 14:21

1 Answer 1

Reset to default
1
$\begingroup$

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

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

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.