10
$\begingroup$

I came across the following question which I haven't seen before:

Question. Fix $k\ge 3$. For infinitely many $n$, does there exists a generating set $\langle R_n \rangle = S_n$, $|R_n|=k$, such that the corresponding (undirected) Cayley graph $\Gamma(S_n,R_n)$ is edge-transitive?

Perhaps, there is a simple explicit combinatorial construction which would work for all large enough $n$ and some fixed $k$. Are there any references I am missing?

NOTE: Now that I see a nice answer by Brendan McKay, let me mention the reason for the question. I just learned the construction of edge-transitive expanders on $S_n$ for some sparse sequence of $n$, but my own simple construction to answer the question above worked only for $n=p+1$, where $p$ is a prime.

$\endgroup$

1 Answer 1

10
$\begingroup$

Here's a partial answer.

Take the generators to be a set of equal length cycles that are disjoint except that they have one point in common. For example $\langle (1,2,3,4), (1,5,6,7), (1,8,9,10)\rangle$. I believe that will generate $S_n$ except where the cycles have odd length (in which case they will generate $A_n$). I didn't prove that but I tried a few cases and expect it is easy. Moreover, it is obvious that the Cayley graph will have automorphisms swapping the generators around.

$\endgroup$
1
  • 3
    $\begingroup$ Yes it generates $A_n$ or $S_n$ according to the length of cycles. Because a transitive subgroup of $S_n$ generated by 3-cycles is $A_n$ (see maths.qmul.ac.uk/~pjc/odds/gps.pdf), and because the commutator of any two of your generators is a 3-cycle (e.g. $(5,1,8)$) consisting of the "root" 1 and two neighbors. Playing with the Schreier graph makes easy to check that 3-cycles generate a transitive subgroup. This completes the proof for all $k\ge 2$ (taking all $n$ of the form $1+qk$ with $q$ odd) $\endgroup$
    – YCor
    Jan 26, 2018 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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