Factorizations of large cycles in the symmetric group

Autor: Dominique Poulalhon, Gilles Schaeffer
Rok vydání: 2002
Předmět:
Zdroj: Discrete Mathematics. 254(1-3):433-458
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(01)00361-2
Popis: The factorizations of an n -cycle of the symmetric group S n into m permutations with prescribed cycle types α 1 ,…, α 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 α 1 ,…, α m ( n ) , 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 genus for factorizations. It turns out that this genus is fully determined by the cycle types α 1 ,…, α m , and that it has a determinant influence on the complexity of computing connection coefficients. In this article, a new formula for c α 1 ,…, α m ( n ) 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.
Databáze: OpenAIRE
Externí odkaz: