Combinatorial properties of block transpositions on Symmetric groups

Annachiara Korchmaros

Published 2015-04-09Version 1

A major problem in the study of combinatorial aspects of permutation groups is to determine the distances in the symmetric group $\Sym_n$ with respect to a generator set. One well-known such a case is when the generator set $S_n$ consists of block transpositions. It should be noted that "the block transposition distance of a permutation" is the distance of the permutation from the identity permutation in the Cayley graph $\Cay$, and "sorting a permutation by block transpositions" is equivalent to finding shortest paths in $\Cay$. The original results in our thesis concern the lower and upper bounds on the block transpositions diameter of $\Sym_n$ with respect to $S_n$ and the automorphism group $\Aut(\Cay)$. A significant contribution is to show how from the toric equivalence can be obtained bijective maps on $\Sym_n$ that we call \emph{toric maps}. Using the properties of the toric maps, we discuss the role of the invariance principle of the block transposition distance within toric classes in the proof of the Eriksson bound. Furthermore, we prove that $\Aut(\Cay)$ is the product of the right translation group by $\textsf{N}\rtimes\textsf{D}_{n+1}$, where $\textsf{N}$ is the subgroup fixing $S_n$ elementwise, and $\textsf{D}_{n+1}$ is a dihedral group whose maximal cyclic subgroup is generated by the toric maps. Computer aided computation supports our conjecture that $\textsf{N}$ is trivial. Also, we prove that the subgraph $\Gamma$ with vertex-set $S_n$ is a $2(n-2)$-regular graph whose automorphism group is $\textsf{D}_{n+1}$. We show some aspects of $\Cay$, notably $\Gamma$ has as many as $n+1$ maximal cliques of size $2$, its subgraph $\Gamma(V)$ whose vertices are those in these cliques is a $3$-regular Hamiltonian graph, and $\textsf{D}_{n+1}$ acts faithfully on $V$ as a vertex regular automorphism group.