6
$\begingroup$

Let $S=\{(1,2),(1,2,3,\ldots,n),(1,2,3,\ldots,n)^{-1}=(1,n\ldots,2)\}$ be a subset of the symmetric group $S_n$. We know that $(1,2,\ldots,n)(1,2)=(2,3,\ldots,n)$, and thus $$[(1,2,\ldots,n)(1,2)]^{n-1}=(1,2,\ldots,n)\overbrace{(1,2)\cdots(1,2,\ldots,n)}^{2n-2}(1,2)=(1).$$ We want to know whether or not there exists another sequence of elements $a_1,a_2,\ldots,a_{2n-4}\in S$ such that $$(12\ldots n)a_{2n-4}a_{2n-5}\cdots a_2a_1(12)=(1),$$ where $a_{i+1}\neq a_i^{-1}$ for $i=0,1,2,\ldots,2n-4$ (putting $a_0=(12)$, $a_{2n-3}=(1,2,\ldots,n)$).

Equivalently, I want to ask if, in the cubic Cayley graph $Cay(S_n,S)$, there is a unique cycle of length $2(n-1)$ passing through $(1)$, $(1,2,\ldots,n)$ and $(1,2)$.

Improve this question
$\endgroup$
5
  • $\begingroup$ should $S$ be the subgroup generated by the three permutations or just the set of the three given permutations? $\endgroup$
    – Amir Sagiv
    Commented Apr 20, 2016 at 16:13
  • 2
    $\begingroup$ you understand $S=S_n$? $\endgroup$
    – Mikhail Ivanov
    Commented Apr 20, 2016 at 16:40
  • 4
    $\begingroup$ @AmirSagiv: If it were meant to be the subgroup generated, then it would be equal to all of $S_n$ (in fact, the first two already generate $S_n$). So surely not: he's asking about expressing the identity as a word in the elements of the subset $S$ with specific constraints. $\endgroup$
    – Arturo Magidin
    Commented Apr 20, 2016 at 17:06
  • $\begingroup$ In other words, you are asking if, in the cubic Cayley graph on $S_n$ with the generators you have given, there is another path of length $2n-4$ between the identity and $(1,n,n-1,\ldots,3)$ besides the one you give... $\endgroup$
    – verret
    Commented Apr 20, 2016 at 20:10
  • 2
    $\begingroup$ For small values of n (n < 10), a computer program should be able to arrive at the answer using a brute force enumeration. Have you tried such? Gerhard "Sometimes Small Informs The Large" Paseman, 2016.04.20. $\endgroup$
    – Gerhard Paseman
    Commented Apr 21, 2016 at 5:06

2 Answers 2

Reset to default
8
$\begingroup$

The smallest $n$ for which there exist sequences as asked for is $n = 7$:

  • $(1,2,3,4,5,6,7) \cdot (1,2) \cdot (1,7,6,5,4,3,2) \cdot (1,2) \cdot (1,2,3,4,5,6,7) \cdot (1,2) \cdot$ $(1,7,6,5,4,3,2) \cdot (1,2) \cdot (1,2,3,4,5,6,7) \cdot (1,2) \cdot (1,7,6,5,4,3,2) \cdot (1,2) = ()$, and

  • $(1,2,3,4,5,6,7) \cdot (1,2,3,4,5,6,7) \cdot (1,2) \cdot (1,7,6,5,4,3,2) \cdot (1,7,6,5,4,3,2) \cdot$ $(1,2) \cdot (1,2,3,4,5,6,7) \cdot (1,2,3,4,5,6,7) \cdot (1,2) \cdot (1,7,6,5,4,3,2) \cdot$ $(1,7,6,5,4,3,2) \cdot (1,2) = ()$.

For $n = 8$ there is no such sequence other than the trivial one mentioned in the question, for $n = 9$ there is one, for $n = 10$ there are $18$, for $n = 11$ there are $5$ and for $n = 12$ there are $104$ such sequences. This has been found with the following GAP function:

SearchXueyiSequences := function ( n )

  local  sequences, search, S;

  search := function ( sequence, a )

    local  b;

    if Length(sequence) = 2*n-3 then
      if sequence[2*n-3] <> (1,2) and Product(sequence)*(1,2) = () then
        Add(sequences,Concatenation(sequence,[(1,2)]));
      fi;
      return;
    fi;
    for b in Difference(S,[a^-1]) do
      search(Concatenation(sequence,[a]),b);
    od;    
  end;

  S := Set(GeneratorsAndInverses(SymmetricGroup(n)));
  sequences := [];
  search([],S[2]);
  sequences := Set(sequences);
  sequences := sequences{[2..Length(sequences)]}; # exclude trivial sequence
  return sequences; 
end;
Improve this answer
$\endgroup$
2
$\begingroup$

For the case $n=3$, take $a_1 = (1,2)$ and $a_2 = (1,3,2)$ instead of $a_1 = (1,2,3)$ and $a_2 = (1,2)$.

A major motivation for posting this answer is to give Xueyi Huang an opportunity to exclude this case in one way or another if it is not really relevant.

Further edit on April 21: As anticipated, Xueyi Huang has made a minor modification to the earlier form of the question and this answer is not a valid answer to the current form of the question.

Improve this answer
$\endgroup$
2
  • $\begingroup$ When $n=3$ and $n=4$, such a sequence is unique by simple computation. I want to know whether the conclusion is true for general $n$. $\endgroup$
    – Xueyi Huang
    Commented Apr 21, 2016 at 2:43
  • 1
    $\begingroup$ You cannot take $a_1=(1,2)$ and $a_2=(1,3,2)$ instead of $a_1=(1,2,3)$ and $a_2=(1,2)$ since they don't satisfy the condition $a_{i+1}\neq a_i^{-1}$. $\endgroup$
    – Xueyi Huang
    Commented Apr 21, 2016 at 3:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .