Factorisations of large cycles in the symmetric group

Dominique Poulalhon Gilles Schaeffer 1
1 ADAGE - Applying discrete algorithms to genomics
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The factorizations of an $n$-cycle of the symmetric group $\Sn$ into $m$ permutations with prescribed cycle types $\a_1,\ldots,\a_m$ describe topological equivalence classes of one pole meromorphic functions on Riemann surfaces. This is one of the motivations for a vast literature on counting such factorizations. Their number, denoted by $c^{(n)}_{\a_1,\ldots,\a_m}$, is also known as a connection coefficient of the center of the algebra of the symmetric group, whose multiplicative structure it describes. The relation to Riemann surfaces induces the definition of a \emph{genus} for factorizations. It turns out that this genus is fully determined by the cycle types $\a_1,\ldots,\a_m$, and that it has a determinant influence on the complexity of computing connection coefficients. In this article, a new formula for $c^{(n)}_{\a_1,\ldots,\a_m}$ is given, that makes this influence of the genus explicit. Moreover, our formula is cancellation--free, thus contrasting with known formulae in terms of characters of the symmetric group. This feature allows us to derive non trivial asymptotic estimates. Our results rely on combining classical methods of the theory of characters of the symmetric group with a combinatorial approach that was first introduced in the much simpler case $m=2$ by Goupil and Schaeffer.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2002, 254 (1-3), pp.433-458
Liste complète des métadonnées

Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:53:00
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48


  • HAL Id : inria-00100937, version 1



Dominique Poulalhon, Gilles Schaeffer. Factorisations of large cycles in the symmetric group. Discrete Mathematics, Elsevier, 2002, 254 (1-3), pp.433-458. 〈inria-00100937〉



Consultations de la notice