# When are (Abelian) Cayley graphs also expanders?

I want to ask the question in two parts,

(1) Is there some fundamental distinguishing property between Abelian and non-Abelian Cayley graphs? (say some specific proof technique which distinguishes them?)

(2) Are there any set of (constant degree) (Abelian) Cayley graphs which are expanders? Do they have any distinguishing property?

For reference one can see chapter 5, starting on page 30 of these notes, http://www.eecs.berkeley.edu/~luca/books/expanders.pdf

• Abelian Cayley graphs have polynomial neighbourhood size, and so cannot be expanders. To be an expander, you have to be able to get from any vertex to any other by following a short path. The difficulty with Abelian groups is that many different paths take you to the same place (following $g$ then $h$ is the same as following $h$ then $g$). To have expansion, you need most of the $N^l$ paths of length $l$ to take you to different places (so the number of places you can get to grows exponentially). In an Abelian gp, you can only get to $l^N$ places, roughly. – Anthony Quas Mar 8 '15 at 2:23
• @AnthonyQuas Can you give a proof (or a reference) to this exact statement about Cayley graphs having a polynomial neighbourhood size? – user6818 Mar 8 '15 at 19:23
• Here's a proof. Suppose there are $d$ generators. Then you are interested in counting the number of distinct group elements you can make by composing $n$ generators. I will give an upper bound on the size of the $n$-ball by only taking account of coincidences that occur by rearrangement; but not any other coincidences. Hence we're asking how many ways are there to pick $n$ items with replacement but without order from $d$. It's a well known combinatorial fact ("stars and bars") that there are $\binom{n+d-1}{d-1}\sim n^{d-1}/(d-1)!$ ways to do this. – Anthony Quas Mar 8 '15 at 20:16
• Also you can see my comment to Sebi Cioba's answer. – user6818 Mar 8 '15 at 22:55

## 1 Answer

To add to Anthony's comment, one can make an explicit connection between the large number of walks between vertices and the spectra of Abelian Cayley graphs. It turns out that constant-degree Abelian Cayley graph are not only bad expanders,but they tend to be disconnected (they have a positive proportion of their eigenvalues close to their valency). See: http://www.math.udel.edu/%7Ecioaba/inpress_version.pdf for a short proof. Alon and Roichman showed earlier that Abelian Cayley graphs have large diameter (power of the order of the graph); the diameter of an expander should be logarithmic in the order of the graph. A proof (using character sums) that the Abelian Cayley graphs have large 2nd eigenvalue is given by Friedman, Murty and Tillich: http://www.mast.queensu.ca/~murty/f-m-t.pdf

• @SebiCioba Is there something about the degree of the Cayley graph becoming logarithmic in the size of the graph if you try to lower the second eigenvalue? (see page 39 of the attached reference in the question) – user6818 Mar 8 '15 at 19:30
• Alon and Roichman "Random Cayley graphs and expanders" math.tau.ac.il/~nogaa/PDFS/exp1.pdf showed that when the degree is logarithmic in the size of the graph, one gets an expander almost always. – Sebi Cioaba Mar 9 '15 at 12:17
• Thanks! I am currently hard-pressed to see how the Abelian group structure says anything about the second highest eigenvalue of the adjacency matrix. I guess reading the Alon-Roichman will provide some insights - but is there something immediate/short/intuitive that you can explain! – user6818 Mar 9 '15 at 18:29
• Anthony's comment gives a good intuition. In my paper, I showed that Abelian Cayley graphs have many closed walks of a given length. Since the trace of the corresponding power of the adjacency matrix equals both the number of closed walks and the sum of the powers of the eigenvalues, this means that some eigenvalues of the graph have to be large. To find a lower bound for the number of closed walks of a given length, you can express it as the number of solutions (ordered tuples) of an equation in the generators. The group being Abelian helps to lower bound this number of solutions. – Sebi Cioaba Mar 10 '15 at 14:03