Cayley graphs of $A_n.$

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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