Equations in Sn and Combinatorial Maps (original) (raw)

Equations in S n and Combinatorial Maps

Gilles Schaeffer

LaBRI, Universit� de Bordeaux I,

Algorithms Seminar

November 3, 1997

[summary by Dominique Gouyou-Beauchamps]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

This talk presents a joint work with Alain Goupil (LACIM-UQAM, Montr�al).

1 Counting Maps

A partition l = (l 1,l2,... ,l_k_) is a finite non-increasing sequence of positive integers l_i_ such that l1�...�l_k_>0. The non-zero terms are called the parts of l and the number k of parts is the length_of l, denoted l (l). We also write l = 1a12a2��� n_a_n when a_i parts of l are equal to i (_i_=1,...,n). When the sum l1+l2+... +l_k_=n, we call n the weight ofl and we write l|- n or |l |=n. The conjugacy classes _C_l of the symmetric group S n are indexed by partitions of n which are called the cycle types of the permutations s� _C_l.

There exit relations between pairs of permutations and maps on oriented surfaces. A map (S,G) on a compact oriented surface S without boundary is a graph_G_ together with an embedding of G into S such that connected components of the complement _S_\ G of the embedding of G in S, called the faces of the map, are homeomorphic to discs. Multiple edges are allowed and our maps are rooted, i.e., one edge of G is distinguished. Two maps (S,G) and (S',G') are isomorphic if there exits an orientation-preserving homeomorphism f:S

� S' such that f(G)=G'. A map is bicolored if its vertices are colored in black or white so that each edge is incident to one vertex of each color. A map is unicellular_if it has one face. The type of a bicolored unicellular map M with_n edges is a pair of partitions (l ,�) whose parts give respective degrees of black and white vertices of M.

Proposition 1 [see [3] for more details] Bicolored unicellular maps of type (l ,�) are maps on a compact orientable surface of genus _g which satisfy _g=g(l ,�) . Moreover, the number Bi (l ,�) of bicolored unicellular maps of type (l ,�) with _n edges is the number of pairs (s ,t) such that s t =(1,2,... ,n) , which is also the coefficient c l ,� (n) that we study below.

Following [7], let z_l=�_i_a_i!i_a_i for a partitionl = 1a12a2��� n_a_n. Then

Example 1 The conjugacy class _T of transpositions is _T=C 1 n-2 2 and |T|= (

) = n!/(n-2)!2 .

In this talk, we are interested with the general problem of computing the number of solutions (a1,... ,a_m_)� C_l1�...�_C_l_m of the equation a1a2��� a_m_=pwhere p is any fixed permutation of S n and where �a1,... ,a_m_� acts transitively on {1,2,... ,n}.

Example 2 Factorization of any _n -cycle into transpositions

If a� C l and a=t 1 ��� t k , then we have k� n-l (l)=� i=1 l (l) (l i -1) and parity of a is given by parity of _n-l (l) . Thus if a 1 a 2 ��� a m =p , we have the first necessary condition for existence of solutions in �(l 1 ,... ,l m ;p) :

If �a1,... ,a_m_� acts transitively on {1,2,... ,n}, the underlying graph is connected.

Example 3 t 1 ��� t m =1 . We need _m=2n-2 transpositions: n-1 transpositions to get an _n -cycle and one connected component, and _n-1 transpositions to return to 1 .

Proposition 2 Let (a 1 ,... ,a m ) be in _C l 1 �...� C l m . If �a 1 ,... ,a m � acts transitively and if a 1 ��� a m =1 , then � i=1 m (n-l (l i ))� 2n-2 .

Definition 1 The genus of _m partitions (l 1 ,... ,l m ) of weight _n is the non negative integer _g defined by the equation

For non transitive systems, we want to compute the number

| d | = | ���� | | (l1,... ,l_m_;p) | ���� | | --- | -- | ---- | | ---------------- | ---- |

of solutions (a1,... ,a_m_)� C_l1�...�_C_l_m of the equation a1a2��� a_m_=pwhere p is any fixed permutation of S n.

We remark that

�^(l1,... ,l_m_;p)= Set (� (l1,... ,l_m_;p)). From this observation we deduce the exponential generating function (in the variables (p j(i)), _j_� 1, 1� i_� m) of �^(l1,... ,l_m;p) for a fixed m:

where _P_l(i)=_p_l1(i)��� p_l_k(i). Hence, in order to obtain the generating function, we only have to know all the _d_l1,... ,l_m_p.

3 Theory of Characters

Detailed proofs for this section can be found in [5, 6].

Theorem 1 [Frobenius formula] Let _G be a finite group. The number of solutions (g 1 ,... ,g m )� C l 1 �...� C l m of the equation _g 1 ��� g m =1 is

where the sum is extended over the irreducible characters of _G .

If G is the symmetric group S n, the irreducible characters are { c�} �|- n and c�(_C_l) can be computed by the Murnaghan-Nakayama rule Hence theoretically _d_l1,... ,l_m_p can be computed since it can be rewritten as where _f_� is the number of standard Young tableaux of shape �. But it is hopeless for _n_� 15.

4 Results for Genus 0

The following results are known.

Theorem 2 [D�n�s theorem] Factorization of an _n -cycle into _n-1 tranpositions: _C T n-1 (n) =n n-2 .

Theorem 3 [Hurwitz formula] Factorization of a of cycle-type (a 1 ,a 2 ,... ,a l (a) ) into a minimal product of _n+l (a)-2 transpositions acting transitively on {1,2,... ,n} :

A new bijective proof without using theory of characters is given in [2].

Theorem 4 [Tree cacti of Goulden and Jackson [4]]

| with | l i =1 | 2 | ��� n | and minimality: | | (n-l (l i ))=n-1. | | ------ | ------------- | --- | ------- | ----------------- | | ------------------------- |

The proof uses a recursive decomposition of tree cacti and the Lagrange-Good inversion.

5 Our Main Theorem

Theorem 5 [A. Goupil and G. Schaeffer] Factorization of an _n -cycle into two permutations of cycle-types l and � with l=(l 1 ,... ,l k ) , �=(� 1 ,... ,� k ) and _l (l)+l (�)=n+1-2g :

| _C | = | | (l (l)-1+2g 1 )!(l (�)-1+2g 2 )!S | (l)S | (�) | | ---- | ---- | | ------------------------------------------- | ------ | ----- |

In [1] this simple expression was derived. This coefficient was later interpreted combinatorially by Goulden and Jackson [4] as the number of unicellular rooted bicolored maps with n edges on a surface of genus zero, the vertices of each color having degree distribution given by l and � respectively, that is the case where _m_=2 in theorem 4.

| If | _g_=1, C | = | ���� | | | + | | ���� | . | | -- | ----------- | -- | ---- | | | - | | ---- | - |

Survey of the proof of Theorem 5:

1. Using explicit expressions for characters of the symmetric group, we give the following formula

   c	=	(-1)r r!(_n_-1-r)!c	c	. (1)

2. The evaluation of some characters are given as weighted summations over set of ``quasi-painted diagrams''.
3. We use a bijection to replace quasi-painted diagrams by properly ``painted diagrams'' and we rewrite Formula (1) as a weighted summation over some ``painted diagram matchings''.
4. The introduction of ``connected components'' of diagram matchings allows to set apart the diagram matching from its painting and to show that the weight depends only on the painting. This is used to apply a sign reversing involution.
5. As expected, the fix-points yield positive contributions. These contributions count ``colorings'' of the diagram matchings.
6. We show that colored diagrams are enumerated by formula of Theorem 5.

6 Corollary for Genus >0

where the sum is taken over the odd c i such that � c _i_=n_-1+2_g.

References

[1]

B�dard (Fran�ois) and Goupil (Alain). -- The poset of conjugacy classes and decomposition of products in the symmetric group. Canadian Mathematical Bulletin, vol. 35, n°2, 1992, pp. 152--160.

[2]

Bousquet-M�lou (M.) and Schaeffer (G.). -- Enumeration of planar constellations. Advances in Applied Mathematics, 1998. -- To appear.

[3]

Cori (Robert) and Mach� (Antonio). -- Maps, hypermaps and their automorphisms: a survey. I, II, III. Expositiones Mathematicae, vol. 10, n°5, 1992, pp. 403--427, 429--447, 449--467.

[4]

Goulden (I. P.) and Jackson (D. M.). -- The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group. European Journal of Combinatorics, vol. 13, n°5, 1992, pp. 357--365.

[5]

Goupil (Alain). -- On products of conjugacy classes of the symmetric group. Discrete Mathematics, vol. 79, n°1, 1989/90, pp. 49--57.

[6]

Jackson (D. M.). -- Counting cycles in permutations by group characters, with an application to a topological problem. Transactions of the American Mathematical Society, vol. 299, n°2, 1987, pp. 785--801.

[7]

Macdonald (I. G.). --Symmetric functions and H all polynomials. -- The Clarendon Press Oxford University Press, New York, 1995, second edition, Oxford Mathematical Monographs, x+475p. With contributions by A. Zelevinsky, Oxford Science Publications.

This document was translated from LATEX byH E V E A.