# 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