An Algorithm for the Factorization of Permutations on a Tree

Abstract

In this paper, we consider a permutation $\sigma \in S_n$ as acting on an arbitrary tree with $n$ vertices (labeled $1,2,3,\dots ,n$). Each edge $[a,b]$ of $T$ corresponds to a transposition $(a,b)\in S_n$, and such a “tree of transpositions” forms a minimal generating set for $S_n$. If $\sigma \in S_n$, then $\sigma$ may be written as a product of transpositions from $T,\sigma =t_k{t}_{k-1}\dots t_2{t}_1$. We will refer to such a product as a $T$-factorization of $\sigma$ of length $k$. The primary purpose of this paper is to describe an algorithm for producing $T$-factorizations of $\sigma$. Although the algorithm does not guarantee minimal factorizations, both empirical and theoretical results indicate that the factorizations produced are “nearly minimal”. In particular, the algorithm produces factorizations that never exceed the known upper bounds.