# Cayley graphs of $A_n.$

Consider the Cayley graphs of $A_n,$ with respect to the generating set of all $3$-cycles. Their properties must be quite well-known, but sadly not to me. For example: what is its diameter? Is it an expander family? (I assume not) Is there a nice description of the eigenvalues? The tree number?

• This looks relevant: arxiv.org/abs/1109.3550 – Aurel Apr 3 '16 at 21:43
• If I have calculated correctly, then the diameter is $\lfloor n/2 \rfloor$. – Derek Holt Apr 3 '16 at 22:13

Here is a quick proof that the diameter of the graph is $\lfloor n/2 \rfloor$.

Note that, when $n$ is odd, the $n$-cycle $(1,2,3,\ldots,n)$ can be expressed as a composite (composing from left to right) of $(n-1)/2$ $3$-cycles: $$(1,2,3)(1,4,5) \cdots (1,n-1,n).$$

When $m$ and $n$ are even with $0 < m < n$, the product of two cycles of even length $(1,2,\ldots,m)(m+1,m+2,\ldots,n)$ can be expressed as a composite of $n/2$ $3$-cycles:$$(1,2,3)(1,4,5) \cdots (1,m,m+1)(m+1,1,m+2)(m+1,m+3,m+4) \cdots (m+1,n-1,n).$$

This gives $\lfloor n/2 \rfloor$ as an upper bound on the diameter.

To get the lower bound, when $n$ is odd, the $3$-cycles used to express $(1,2,\ldots,n)$ must involve all points $1,2,\ldots,n$ and they must be connected, so we need at least $(n-1)/2$ of them.

When $n$ is even, it is not possible to express the individual cycles in $(1,2,\ldots,m)(m+1,m+2,\ldots,n)$ as composites of $3$-cycles because they are odd permutations, so again the $3$-cycles in a decomposition of this permutation must be connected and hence we need at least $n/2$ of them.

For $n\geq 5$, all the eigenvalues of the Cayley graph you describe are integers. The eigenvalues correspond to character values on $3$-cycles multiplied by the number of $3$-cycles (because the generating set of $3$-cycles is a conjugacy class). The multiplicity is the dimension of the irreducible representation.

Since the character values are algebraic integers, it is enough to observe that on a $3$-cycle all character values are rational. This follows from the well-known fact (see Noam Elkies answer to this question) that if $g$ is an element of a finite group $G$, then $\chi(g)$ is rational for all characters $\chi$ of $G$ if and and only if $g^m$ is conjugate to $g$ for all powers $m$ coprime to the order of $g$.

Since every power of a $3$-cycle that is not the identity is a $3$-cycle and $3$-cycles are all conjugate in $A_n$ for $n\geq 5$, this gives the integrality of character values on $3$-cycles.

• You could also note that when $n \geq 5$, every $3$-cycle of $A_{n}$ is conjugate to its inverse via a product of two disjoint transpositions. For example, $(123)$ is inverted by $(12)(45)$. – Geoff Robinson Apr 4 '16 at 21:20

As soon as the generating set of a Cayley graph of a group $G$ is a union of conjugacy classes of $G$, the graph lives in the commutative association scheme of these classes, where the multiplication is determined by the character table of $G$. Thus things like diameter, eigenvalues, can be determined from the character table, although this is not necessarily trivial.

Just for fun, I computed the eigenvalues of this graph for $G=A_n$, $n=15$, and they are all integers. Not sure if this is easy to explain...

Given a conjugacy class $C$ of the alternating group ${\rm A}_n$ ($n \geq 5$), for every $\delta \in ]0,1[$ there is a constant $c(\delta) > 0$ such that if the number of points moved by an element of $C$ is at least $\delta n$, then the undirected Cayley graph $X({\rm A}_n,C)$ is a $c$-expander. A family of such Cayley graphs where the number of points moved by an element of $C$ is $o(\sqrt{n})$ is not a family of $c$-expanders. See

Yuval Roichman. Expansion Properties of Cayley Graphs of the Alternating Groups, Journal of Combinatorial Theory, Series A, Volume 79(1997), Issue 2, Pages 281–297.

• Isn't it true that as soon as the number of points moved is $o(n)$, then the graph is not an expander? Let $S$ be the set of permutations with at least one fixed point. Then $S$ has constant density, and if I hit a random element of $S$ with a random element of $C$ then with probability $1-o(1)$ the result is again in $S$. – Sean Eberhard Apr 4 '16 at 9:48

In general, The eigenvalues of a Cayley graph of a group $G$ with respect to a subset $S$ can be computed using irreducible representations of $G$. In particular, using character table of $G$ when $S$ is a union of conjugacy Classes of $G$. For example, see my paper, "M. Arezoomand and B.Taeri,on the characteristic polynomial of n-Cayley digraphs, Electron. J. Combin. 2013."

• Can you prove @DimaPasechnik's experimental observation that the eigenvalues are integers? – Igor Rivin Apr 4 '16 at 10:56
• Benjamin's answer does prove it. – Dima Pasechnik Apr 5 '16 at 20:13