7
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 12
    $\begingroup$ 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. $\endgroup$
    – Anthony Quas
    Commented Mar 8, 2015 at 2:23
  • $\begingroup$ @AnthonyQuas Can you give a proof (or a reference) to this exact statement about Cayley graphs having a polynomial neighbourhood size? $\endgroup$
    – user6818
    Commented Mar 8, 2015 at 19:23
  • 3
    $\begingroup$ 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. $\endgroup$
    – Anthony Quas
    Commented Mar 8, 2015 at 20:16
  • $\begingroup$ Also you can see my comment to Sebi Cioba's answer. $\endgroup$
    – user6818
    Commented Mar 8, 2015 at 22:55

2 Answers 2

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ @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) $\endgroup$
    – user6818
    Commented Mar 8, 2015 at 19:30
  • 2
    $\begingroup$ 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. $\endgroup$
    – Sebi Cioaba
    Commented Mar 9, 2015 at 12:17
  • $\begingroup$ 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! $\endgroup$
    – user6818
    Commented Mar 9, 2015 at 18:29
  • 2
    $\begingroup$ 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. $\endgroup$
    – Sebi Cioaba
    Commented Mar 10, 2015 at 14:03
2
$\begingroup$

For what it's worth, a stronger statement is possible. Suppose $(G_n)$ is a sequence of finite groups. Moreover, suppose that there is an integer $k$ such that for all $n$, the derived length of $G_n$ is less than or equal to $k$. Then $(G_n)$ does not admit a bounded-degree expander family. That's due to Lubotzky and Weiss in "Groups and Expanders." It appears as Cor. 3.3. An explication of this proof, as well as an additional proof, can be found in this book. For $k=1$, this reduces to the statement above about abelian groups.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .