MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

First, a definition: a girth relator for a Cayley graph is a word that you get by reading the edge labels along a shortest loop. The girth relator is not usually unique, though it is often unique up to cyclic conjugating. Now the question: what is the smallest girth that a Cayley graph of the alternating group Alt(n) can have, given that no girth relator is a proper power? Without the restriction on the girth relator, the answer is 2, since you can always take one of the generators to be of order 2. With the restriction on the girth relator, it is not clear that there is a universal upper bound, the answer might depend on n. None the less, I suspect the answer is 6.

share|cite|improve this question
from topology point of view, you might want to disregard length 2 loops. – Dima Pasechnik Aug 18 '14 at 6:37
6? Why? Why not 42? :) – Dima Pasechnik Aug 18 '14 at 6:38
If you allow for redundant generating sets, the answer is 3: Take two elements $\pi, \sigma$, which generate $A_n$, and take the Cayley graph with respect to $\{\pi, \sigma, \sigma^{-1}\pi^{-1}\}$. Unless the order of $\pi, \sigma$ or $\pi\sigma$ is $\leq 3$, you get a loop of length 3, but no girth relator is a proper power. – Jan-Christoph Schlage-Puchta Aug 18 '14 at 9:09

If you exclude trivial examples, which lead to girth 3, then for sufficiently large $n$ the answer is 4.

Assume for simplicity that $n$ is odd.

Suppose there exists a prime number $p$ with $n/2<p\leq n-9$. Then write $n+2=p+a+b$, where $a, b$ are both odd and $\geq 5$. Consider the generating triple $\pi=(12..a), \sigma = (a\,a+1\,\ldots n-b+1), \tau = (n-b+1\,n-b+2\ldots n)$, that is, an $a$-cycle, a $b$-cycle and a $p$-cycle. Clearly $G=\langle\pi, \sigma, \tau\rangle$ is transitive. Since $G$ contains a $p$-cycle with $p>n/2$, $G$ is primitive, and since it contains a $p$-cycle of length $<n-5$, $G$ is one of $A_n, S_n$. Since $G$ is generated by cycles of odd length, we conclude that $\{\pi,\sigma,\tau\}$ is indeed a generating triple.

Since $\pi$ and $\tau$ commute, the Cayley graph contains the loop $[\pi,\tau]$ of length 4. All generators have order $>4$, and the same holds true for the product of any two generators. Hence this Cayley graph has girth 4 without a girth relator being a proper power.

If $n$ is even, one can increase the overlap between the support of $\sigma$ and $\tau$, one only has to make sure that the products $\sigma\tau,\sigma\tau^{-1}$ do not get order 2, which is certainly possible.

Suppose there exists a loop of length 2 or 3. Then we want to show that this loop is either a power or redundant. If the length is 2, the loop is $ab$ with $b=a^{-1}$, thus either the generating system contains an element together with its inverse, and is therefore redundant, or $a$ has order 2, and this loop is a power. If the length is 3, and the loop is $abc$, then either $c$ is none of $a,b$, in which case $c$ is redundant, or, up to symmetry, we have $a^2b, aba, a^3$. The last case gives a power, the second is conjugate to $a^2b$, and $a^2b$ shows that $b$ is redundant.

Hence 2 and 3 cannot occur, while 4 occurs for all large $n$. It seems to me that large means $n\geq 20$, so checking the smaller cases should be doable.

share|cite|improve this answer
oops, forgot a critical condition: I want the answer for the 2-generator case. – moshe newman Aug 18 '14 at 19:33
@moshenewman: Then you may ask a new question -- this one has been answered satisfactorily, as far as I see. – Stefan Kohl Aug 19 '14 at 8:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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