Inequivalent Transitive Factorizations into Transpositions

Goulden, I. P. ; Jackson, D. M. ; Latour, F. G.

Canadian journal of mathematics, Tome 53 (2001) no. 4, pp. 758-779

Résumé

The question of counting minimal factorizations of permutations into transpositions that act transitively on a set has been studied extensively in the geometrical setting of ramified coverings of the sphere and in the algebraic setting of symmetric functions.It is natural, however, from a combinatorial point of view to ask how such results are affected by counting up to equivalence of factorizations, where two factorizations are equivalent if they differ only by the interchange of adjacent factors that commute. We obtain an explicit and elegant result for the number of such factorizations of permutations with precisely two factors. The approach used is a combinatorial one that rests on two constructions.We believe that this approach, and the combinatorial primitives that have been developed for the “cut and join” analysis, will also assist with the general case.

Détail

DOI : 10.4153/CJM-2001-031-x

Mots-clés : 05C38, 15A15, 05A15, 15A18, transitive, transposition, factorization, commutation, cut-and-join

Bibliographie

[A] Arnol’d, V. I., Topological classification of trigonometric polynomials and combinatorics of graphs with an equal number of vertices and edges. Functional Anal. Appl. 30(1996), 1–14. Google Scholar

[BIZ] Bessis, D., Itzykson, C. and Zuber, J. B., Quantum Field Theory Techniques in Graphical Enumeration. Adv. in Appl. Math. 1(1980), 109–157. Google Scholar

[CF] Cartier, P. and Foata, D., Problèmes combinatoires de commutation et réarrangements. Lecture Notes in Math. , Springer-Verlag, Berlin, 1969. Google Scholar

[E] Eidswick, J. A., Short factorizations of permutations into transpositions. Discrete Math. 73(1989), 239–243. Google Scholar

[ELSV] Ekedahl, T., Lando, S., Shapiro, M. and Vainshtein, A., On Hurwitz numbers and Hodge integrals. C. R. Acad. Sci. Paris Sér. I Math. 328(1999), 1175–1180. Google Scholar

[FP] Fantechi, B. and Pandharipande, R., Stable maps and branch divisors. math.AG/9905104. Google Scholar

[GJ1] Goulden, I. P. and Jackson, D. M., Symmetric functions and Macdonald's result for top connexion coefficients in the symmetric group. J. Algebra 166(1994), 364–378. Google Scholar

[GJ2] Goulden, I. P. and Jackson, D. M., Transitive factorisations into transpositions and holomorphic mappings on the sphere. Proc. Amer.Math. Soc. 125(1997), 51–60. Google Scholar

[GJ3] Goulden, I. P. and Jackson, D. M., Combinatorial Enumeration. Wiley Interscience, New York, 1983. Google Scholar

[GJV] Goulden, I. P., Jackson, D. M. and Vakil, R., The Gromov-Witten potential of a point, Hurwitz numbers and Hodge integrals. Proc. LondonMath. Soc., (to appear). Google Scholar

[H] Hurwitz, A., Ueber Riemann’sche Flächen mit gegebenen Verzweigungspunkten. Math. Ann. 39(1891), 1–61. Google Scholar

[L] Longyear, J. Q., A peculiar partition formula. Discrete Math. 78(1989), 115–118. Google Scholar

[M] Macdonald, I. G., Symmetric functions and Hall polynomials. Second Edition, Clarendon Press, Oxford, 1995. Google Scholar

[S] Stanley, R. P., Factorization of a permutation into n-cycles. Discrete Math. 37(1981), 255–262. Google Scholar