Does a classification of simultaneous conjugacy classes in a product of symmetric groups exist?

Question

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

Answer 1

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.

Answer 2

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
cl:=ConjugacyClasses(g);;
MorClassLoop(g,[cl,cl],rec(),8);

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