Let the symmetric group $S_n$ on $n$ letters act on $S_n^d=S_n\times\cdots\times S_n$ by simultaneous conjugation, i.e. $\pi\in S_n$ acts on $(\sigma_1,\ldots,\sigma_d)\in S_n^d$ by $\pi.(\sigma_1,\ldots,\sigma_d)=(\pi\sigma_1\pi^{-1},\ldots,\pi\sigma_d\pi^{-1})$.

I would like to know if there is a classification (a combinatorial description) of the orbits of this action, at least in the case $d=2$. For $d=1$, a combinatorial description is given by the cycle structure of the permutation.

There is a related question that deals with deciding whether two elements of $S_n^d$ are in the same orbit and the author of that question also defines a canonical representative for each orbit, but it is quite indirect. It seems to me that a classification for arbitrary $d$ is probably not known.

In another related question, the number of orbits is discussed, but I am really interested in a combinatorial description that classifies them.

Edit. To clarify what I mean by "combinatorial description": At the very least, I am looking for an algorithm that enumerates exactly one representative from each simultaneous conjugacy class in $S_n^d$ with polynomial delay (polynomial in $n$ and $d$ will be fine).

  • $\begingroup$ When $d$ is $1$ the number of conjugacy classes grows like $n^{-1}\exp(n^{1/2})$ (with various scalars I am not writing) so you cannot enumerate them in polynomial time in $n$. $\endgroup$ Oct 19, 2014 at 19:28
  • $\begingroup$ @MarianoSuárez-Alvarez: No, but I can do so with polynomial delay. $\endgroup$ Oct 19, 2014 at 22:04

2 Answers 2


For the sake of simplicity, consider only the case $d=2$. In this case, two pairs $(a,b), (a,c) \in {\rm S}_n^2$ lie in the same orbit if and only if there is a permutation $\pi$ in the centralizer of $a$ which conjugates $b$ to $c$.

Therefore in order to obtain a nice combinatorial description of the orbit of $(a,b)$, we would need to get control over the conjugates of $b$ under the elements of the centralizer of a permutation $a$ with possibly completely different cycle structure than $b$.

My feeling is that in contrast to mere orbit counting or algorithmic membership tests, this is too complicated to allow a nice solution. Of course this is not an exact answer -- just like asking for a "combinatorial description" is not precise.

  • $\begingroup$ I added an edit that explains what I mean by a combinatorial description. I hope it's precise enough. $\endgroup$ Oct 17, 2014 at 14:28
  • $\begingroup$ @JeskoHüttenhain: o.k. -- if you allow an algorithm, this looks more feasible. (My impression was that you are looking for an answer analogous to that in case $d=1$). $\endgroup$
    – Stefan Kohl
    Oct 17, 2014 at 15:50
  • $\begingroup$ Indeed, an answer analogous to the case $d=1$ would have been optimal, because it yields an efficient algorithm to enumerate precisely one representative from each orbit - but indeed, the latter is the actual goal, I should have said that. $\endgroup$ Oct 18, 2014 at 0:17

You can find representatives of the orbits algorithmically by choosing $\sigma_1$ by $S_n$ conjugacy, $\sigma_2$ as representative up to conjugacy by the centralizer of $\sigma_1$, and so on.

If $C=C_{S_n}(\sigma_1)$, then the $C$-orbits on $S_n$ refine the $S_n$-orbits of $S_n$ (i.e. the conjugacy classes of $S_n$), the refinement of the class containing $\tau$ corresponds to the double cosets $C_{S_n}(\tau)\setminus S_n / C$.

The following commands in GAP use this method (essentially I'm asking it to enumerate homomorphisms from the free group into $S_n^d$), i.e. you get a list of orbit representative tuples:

g:=SymmetricGroup(6); # or whatever degree

The number of repetitions of cl indicates the value of $d$, that is use [cl,cl,cl] for $d=3$ and so on. Please note that this is calling an internal function with limited error check. It might not work for $n<3$ or $d=1$.

  • $\begingroup$ Which algorithm is used to perform this enumeration? Are you certain that it enumerates each representatives with only polynomial delay? $\endgroup$ Oct 19, 2014 at 22:03
  • $\begingroup$ The algorithm is the one I described -- double cosets of centralizers (I call it ``morpheus'' as it is used for homomorphism search, but it must have been discovered many times). Since both centralizer (not just representatives, but iterated) as well as double cosets are not know to be polynomial, it is not polynomial time. It is not obvious to see whether or not it is polynomial delay. $\endgroup$
    – ahulpke
    Oct 20, 2014 at 2:30

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.