16
$\begingroup$

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?

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

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Geoff Robinson Apr 4 '16 at 21:20
10
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Sean Eberhard Apr 4 '16 at 9:48
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.