Cordelia Li, University of Washington
-
PDL C-401
Given a permutation in S_n, one can ask how many ways to decompose it into a minimal-length, transitive product of transpositions. We show that the number of minimal transitive factorizations of the identity permutation in S_n into transpositions supported on a given quasi-threshold graph G is always divisible by (2n-2)!/n!, generalizing results of Hurwitz for the complete graph and Pak for the star graph. We give a combinatorial formula for the quotient as a sum over certain weighted spanning trees of G called factorization trees.