# Combinatorial interpretation and positivity of Kerov's character polynomials

Valentin Féray

Laboratoire d'Informatique de l'Institut Gaspard Monge, Université de Paris-Est Marne La Vallée, 5 boulevard Descartes, 77 454 Marne-La-Vallée Cedex 2, France, feray@univ-mlv.fr

**Abstract.** Kerov's polynomials give irreducible character values of the symmetric group in term of the free cumulants of the associated Young diagram. Using a combinatorial approach with maps, we prove in this article a positivity result on their coefficients, which extends a conjecture of S. Kerov.

**Résumé.** Les polynômes de Kerov expriment les valeurs des caractères irréductibles du groupe symmétrique en fonction des cumulants libres du diagramme de Young associé. Grâce à une approche combinatoire à base de cartes, nous prouvons dans cet article un résultat de positivité sur leurs coefficients, qui généralise une conjecture de S. Kerov.

**Keywords:** Representations, symmetric group, maps

# 1 Introduction

## 1.1 Irreducible characters of the symmetric group

If $\sigma$ is a permutation in $S(k)$, let $C(\sigma)$ be the partition of the set $[k] := \{1, \dots, k\}$ in orbits under the action of $\sigma$. The type of $\sigma$ is, by definition, the partition $\mu$ of the integer $k^{(i)}$ whose parts are the length of the cycles of $\sigma$. The conjugacy classes of $S(k)$ are exactly the sets of partition of a given type. Irreducible representations of $S(n)$ are indexed by partitions $\lambda$ of $n$, or equivalently by Young diagrams of size $n$. Let us define, for $\mu \vdash k$ and $\lambda \vdash n$ with $k \le n$, the following normalization of character values:

$$ \Sigma_{\mu}(\lambda) := \frac{n(n-1)\cdots(n-k+1)\chi^{\lambda}(\sigma)}{\chi^{\lambda}(Id_n)}, \qquad (1) $$

where $\sigma$ is a permutation in $S(k)$ of type $\mu$ (and can be seen as a permutation in $S(n)$ of type $\mu 1^{n-k}$) and $\chi^{\lambda}$ is the character value of the irreducible representation associated to $\lambda$ (see [Ma]).

We use in this paper a new way to look at Young diagrams, initiated by R. Stanley in [St1]. In this paper, he proved a nice combinatorial formula for character values, but only for Young diagrams of rectangular

<footnote>(i) A partition of $k$ is a non-increasing sequence of non-negative integers of sum $k$.</footnote>
shape. To generalize it, we have to look at any Young diagram as a superposition of rectangles: if **p** and **q** are two finite sequences of positives integers

$$ \lambda(\mathbf{p}, \mathbf{q}) := \left( \underbrace{\sum_{i \ge 1} q_i, \dots, \sum_{i \ge 1} q_i}_{\text{$p_1$ times}} ; \underbrace{\sum_{i \ge 2} q_i, \dots, \sum_{i \ge 2} q_i}_{\text{$p_2$ times}} \right) $$

**Theorem 1.1.1 (Stanley, Féray, Śniady 2006)** Let **p** and **q** be two finite sequences, $\lambda(\mathbf{p}, \mathbf{q}) \vdash n$ the associated Young diagram and $\mu \vdash k(k \le n)$. If $\sigma \in S(k)$ is a permutation of type $\mu$, the character value is given by the formula:

$$ \Sigma_{\mu}(\lambda(\mathbf{p}, \mathbf{q})) = \sum_{\substack{\tau, \bar{\tau} \in S(k) \\ \tau \bar{\tau} = \sigma}} (-1)^{|C(\tau)|+l(\mu)} N^{\tau, \bar{\tau}}(\mathbf{p}, \mathbf{q}), \quad (2) $$

where $l(\mu)$ is the number of parts of $\mu$ and $N^{\tau, \bar{\tau}}$ a homogeneous power series of degree $|C(\tau)|$ in **p** and $|C(\bar{\tau})|$ in **q** which will be defined in section 2.

The complexity of this formula depends only on the size of the support of the permutation, (and not of the permutation itself).

## 1.2 Free cumulants

To solve asymptotic problems in representation theory of the symmetric groups, P. Biane introduced in [Bi2] the free cumulants $R_i(\lambda)$ (of the transition measure) of a Young diagram<sup>(ii)</sup>: the $l+1$-th free cumulant of $\lambda$ is the leading term of $\Sigma_{(l)}(\lambda)$, when $l$ is fixed and the size of $\lambda$ grows to infinity (for a precise statement, see [Bi2]). This result, together with theorem 1.1.1 and the fact that $R_{l+1}$ is homogeneous of degree $l+1$ in **p** and **q**, gives a combinatorial formula for cumulants:

$$ R_{l+1}(\lambda(\mathbf{p}, \mathbf{q})) = \sum_{\substack{\tau, \bar{\tau} \in S(l) \\ \tau \bar{\tau} = (1 \dots l) \\ |C(\tau)| + |C(\bar{\tau})| = l+1}} (-1)^{|C(\tau)|+1} N^{\tau, \bar{\tau}}(\mathbf{p}, \mathbf{q}) \quad (3) $$

## 1.3 Kerov's polynomials

It is natural to wonder if there are exact expressions of character values in terms of free cumulants. Kerov's polynomials give a positive answer to this question for character values on cycles (they appear first in a paper of P. Biane [Bi3, Theorem 1.1] in 2003) and can be generalized to any permutation:

**Definition-Theorem 1.3.1** For any $\mu \vdash k$, there exists a polynomial $K_\mu$, with integer coefficients, such that, for every Young diagram $\lambda$ of size bigger than $k$, one has:

$$ \Sigma_{\mu}(\lambda) = K_{\mu}(R_{2}(\lambda), \dots, R_{k+1}(\lambda)). \quad (4) $$

<footnote><sup>(ii)</sup> The transition measure of a Young diagram is a measure on the real line introduced by S. Kerov in [Ke]. Its free cumulants are a sequence of real numbers associated to this measure. The denomination comes from free probability theory, see [Bi2] for more details.</footnote>
$$
\begin{align*}
\text{Examples:} \qquad & \Sigma_3 = R_4 + R_2; \\
\Sigma_1 &= R_2; \qquad \Sigma_4 = R_5 + 3R_3; \\
\Sigma_2 &= R_3; \qquad \Sigma_5 = R_6 + 15R_4 + 5R_2^2 + 8R_2; \\
\Sigma_{2,2} &= R_3^2 - 4R_4 - 2R_2^2 - 2R_2; \\
\Sigma_{3,2} &= R_3 \cdot R_4 - 5R_2 \cdot R_3 - 6R_5 - 18R_3; \\
\Sigma_{2,2,2} &= R_3^3 - 12R_3 \cdot R_4 - 6R_3 \cdot R_2^2 + 58R_3 \cdot R_2 + 40R_5 + 80R_3.
\end{align*}
$$

For original Kerov's polynomials (when $\mu$ has only one part), the positivity of coefficients can be observed by numerical computations and was conjectured by S. Kerov. A lot of work has been done to understand these coefficients ([Bi3],[Śn],[GR],[Bi4],[RŚ]): a general, but exploding in complexity, explicit formula and a combinatorial interpretation for linear terms in free cumulants have been found. The main result of this paper is their positivity and a generalization to any partition $\mu$ (conjectured in [RŚ] in a different form).

**Theorem 1.3.2** Let $\mu \vdash k$ and $\sigma \in S(k)$ a permutation of type $\mu$. Let

$$
\Sigma'_{\mu} := \sum_{\substack{\tau, \bar{\tau} \in S(k) \\ \frac{\tau \bar{\tau}}{\tau \bar{\tau}} = \sigma \\ <\tau, \bar{\tau}> \text{ trans.}}} (-1)^{|C(\tau)|+1} N^{\tau, \bar{\tau}}, \quad (5)
$$

where $<\tau, \bar{\tau}> \text{trans.}$ means that the subgroup $<\tau, \bar{\tau}>$ of $S(k)$ generated by $\tau$ and $\bar{\tau}$ acts transitively on the set $[k]$. Then there exists a polynomial $K'_{\mu}$ with **non-negative** integer coefficients such that, as power series in $\mathbf{p}$ and $\mathbf{q}$:

$$
\Sigma'_{\mu} = K'_{\mu}(R_2, \dots, R_{k+1}). \quad (6)
$$

In the case where $\mu = (k)$, one has $\Sigma'_{(k)} = \Sigma_{(k)}$ and the theorem is exactly Kerov's positivity conjecture (equality as power series in $\mathbf{p}$ and $\mathbf{q}$ is equivalent to equality for all Young diagram $\lambda$, whose size is bigger than a given number). This theorem is the purpose of this paper and the proof is only sketched in this extended abstract.

$$
\begin{align*}
\text{Examples: } \Sigma'_{2,2} &= 4R_4 + 2R_2^2 + 2R_2; \\
\Sigma'_{3,2} &= 6R_2 \cdot R_3 + 6R_5 + 18R_3; \\
\Sigma'_{2,2,2} &= 64R_3 \cdot R_2 + 40R_5 + 80R_3.
\end{align*}
$$

It is easy to recover $\Sigma$ from $\Sigma'$ by looking, for each factorization $\tau \cdot \bar{\tau} = \sigma$, at the set partition of $[k]$ in orbits under the action of $<\tau, \bar{\tau}>$ (one has to be careful about the signs):

$$
\Sigma_{\mu} = \sum_{\Pi \text{ partition of } [l(\mu)]} \left( \prod_{\{i_1, \dots, i_l\} \text{ part of } \Pi} (-1)^{l-1} \Sigma'_{\mu_{i_1}, \dots, \mu_{i_l}} \right). \quad (7)
$$
## 1.4 Organization of the article

In section 2, we will associate a map to each pair of permutations. This will help us to define the associated power series $N$. In section 3, for any map $M$, we write $N(M)$ as an algebraic sum of power series appearing in the combinatorial expression of cumulants. Thanks to this decomposition, in section 4, we sketch the proof of theorem 1.3.2 and give the value of some particular coefficients.

# 2 Maps and polynomials

In this section, we define the power series $N^{\tau, \bar{\tau}}$ as the composition of three functions:

$$S(k) \times S(k) \xrightarrow{\text{§ 2.1}} \text{bicolored labeled map} \xrightarrow{\text{Forget}} \text{bicolored graph} \xrightarrow{\text{§ 2.2}} \mathbb{C}[[\mathbf{p}, \mathbf{q}]]$$

## 2.1 From permutations to maps

The following construction is classical (it generalizes the work of I.P. Goulden and D.M. Jackson in [GJ]) but we recall it for completeness.

**Definition 2.1.1** A graph is a set of vertices $V$, a set of half-edges $H$ partitioned in sets of cardinal 2 called edges and sets of cardinal 1 called external half-edges and a fonction extremity from $H$ to $V$. A map is a graph endowed with, for each vertex $v$, a cyclic order on the half-edges of extremity $v$.

**Definition 2.1.2** To an edge-labeled bicolored map $M$ with $k$ edges, we associate the pair of permutations $(\tau, \bar{\tau}) \in S(k)^2$ defined by: if $i$ is an integer in $[k]$, $e$ the edge of $M$ with label $i$ and $h$ its half-edge with a white (resp. black) extremity$^{(iii)}$, then $\tau(i)$ (resp. $\bar{\tau}(i)$) is the label of the edge containing the successor of $h$ (i.e. the half-edge following $h$ in the cyclic order given by its extremity).

It is easy to see that this defines a bijection between edge-labeled bicolored maps and pairs of permutations. Its inverse associates to a pair of permutations $(\tau, \bar{\tau}) \in S(k)^2$ the following bicolored edge-labeled map $M^{\tau, \bar{\tau}}$: the set of white vertices is $C(\tau)$, the one of black vertices $C(\bar{\tau})$, the set of half-edges $\{1^w, 1^b, \dots, k^w, k^b\}$ is partitioned in edges $\{i^w, i^b\}$ and the cycle $(i_1, \dots, i_l)$ of $\tau$ (resp. $(j_1, \dots, j_l)$ of $\bar{\tau}$) is the extremity of the half-edges $i_1^w, \dots, i_l^w$ (resp. $j_1^b, \dots, j_l^b$) in this cyclic order.

**Example 1** The map from figure 1 is associated to the pair $((15)(27)(3)(486), (174)(236)(58))$ of permutations in $S(8)$, (written as product of cycles of disjoint support).

Note that the connected components of $M^{\tau, \bar{\tau}}$ are in bijection with the orbits of $[k]$ under the action of $\langle \tau, \bar{\tau} \rangle$. So, a factorization is transitive if and only if its map is connected. In particular, maps of factorizations appearing in formula (3) (the combinatorial expression for cumulants) are connected maps with $k+1$ vertices and $k$ edges, that is to say planar trees.

## 2.2 From graphs to polynomials

**Definition 2.2.1** Let $G$ be a bicolored graph and $V$ its set of vertices, disjoint union of the black vertices $V_b$ and the white ones $V_w$. An evaluation $\psi: V \to \mathbb{N}^*$ is called admissible if, for any edge between a

<footnote>(iii) By definition, the two half-edges of an edge of a bicolored graph have respectively a white and a black extremity.</footnote>
<figure><img src="image_1.png" /><figcaption>Fig. 1: Map of the pair ((15)(27)(3)(486), (174)(236)(58))</figcaption></figure>

white vertex w and a black one b, it fulfills $\psi(b) \ge \psi(w)$. The power series $N(G)$ in indeterminates p and q is defined by the formula:

$$N(G) = \sum_{\substack{\psi: V \to \mathbb{N} \\ \text{admissible}}} \prod_{w \in V_w} p_{\psi(w)} \prod_{b \in V_b} q_{\psi(b)}. \qquad (8)$$

Note that $N$ is extended by $\mathbb{Z}$-linearity, to the ring $A_{bg}$ spanned by bicolored graphs. It is in fact a morphism of rings (the power series associated to a disjoint union of graphs is simply the product of the power series associated to these graphs).
If $\tau$ and $\bar{\tau}$ are two permutations in $S(k)$, we put:

$$N^{\tau, \bar{\tau}} := N(M^{\tau, \bar{\tau}}).$$

This definition is the one that appears in theorem 1.1.1. The main step of our proof of Kerov's conjecture is to write the power series associated to any pair of permutations as an algebraic sum of power series associated to forests (product of the terms appearing in the combinatorial expression of cumulants, see (3)).

Let $G$ be a bicolored graph and $L$ an oriented loop<sup>(iv)</sup> of $G$. We denote by $E(L)$ the set of edges which appear in the sequence $L$ oriented from their white extremity to their black one. Let us define the following element of the $\mathbb{Z}$-module $A_{bg}$:

$$T_L(G) = \sum_{\substack{E' \subset E(L) \\ E' \neq \emptyset}} (-1)^{|E'|-1} G \setminus E', \qquad (9)$$

where $G \setminus E'$ denotes the graph obtained by taking $G$ and erasing its edges belonging to $E'$ (it is a subgraph of $G$ with the same set of vertices). These elementary transformations are drawn on figure 2, where we have only drawn vertices and edges belonging to the loop $L$ (so these schemes can be understood as local transformations).

We have the following conservation property (easy to prove):

<footnote><sup>(iv)</sup> An oriented loop is by definition a cyclic sequence of oriented edges such that the end of each edge is the origin of the next one, and such that the ends of all edges are different.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 2: Illustration of transformation $T_L$</figcaption></figure>

**Proposition 2.2.1** If $G$ is a bicolored graph and $L$ an oriented loop of $G$, then

$$N(T_L(G)) = N(G). \qquad (10)$$

Recall that $N$ is a morphism of rings, so $(\mathbb{A}_{bg})_{KerN}$ is a ring.

**Corollary 2.2.2** The ring $(\mathbb{A}_{bg})_{KerN}$ is generated by trees.

**Proof:** Just iterate the proposition by choosing any oriented loop until there is no loop left (if a graph is not a disjoint union of trees, there is always one). □

However, forests are not linearly independent in $(\mathbb{A}_{bg})_{KerN}$.

# 3 Map decomposition

By iterating proposition 2.2.1 until there are only forests left, given a graph $G$, we obtain an algebraic sum of forests whose associated power series is $N(G)$. But there are many possible choices of oriented loops and they can give different sums of forests. In this section, we explain, how, by restricting the choices, we choose a particular one, which depends on the map structure and the labeling.

## 3.1 Elementary decomposition

To do coherent choices, it is convenient to add an external half-edge to our map (an external half-edge has an extremity but does not belong to any edge). So, in this paragraph, we deal with bicolored maps with exactly one external half-edge $h$. They generate a free $\mathbb{Z}$-module denoted $\mathbb{A}_{bm,1}$.

If $M$ is such a map, let $\star$ be the extremity of its external half-edge. An (oriented) loop $L = (e_1, \dots, e_h)$ is called admissible if:

* The vertex $\star$ is a vertex of the loop, that is to say that $\star$ is the extremity of the second half-edge $h_{i,2}$ of $e_i$ and of the first half-edge $h_{i+1,1}$ of $e_{i+1}$ for some $i$ (where $L = e_1, \dots, e_h$, with the convention $e_{h+1} = e_1$);
<figure><img src="image_3.png" /><figcaption>Fig. 3: General form of the connected component containing ⋆ of a map appearing in $D_1(M)$.</figcaption></figure>

• The cyclic order at ⋆ restricted to the set $\{h, h_{i,2}, h_{i+1,1}\}$ is the cyclic order $(h, h_{i+1,1}, h_{i,2})$.

If $L$ satisfies the first condition, exactly one among the oriented loops $L$ and $L'$ is admissible (where $L'$ is $L$ with the opposite orientation).

**Definition-Theorem 3.1.1** There exists a unique linear operator

$$D_1 : \mathbb{A}_{bm,1} \to \mathbb{A}_{bm,1}$$

such that:

• The image of a given map $M$ lives in the vector space spanned by its submaps with the same set of vertices.

• If $L$ is an admissible loop of $M$, then

$$D_1(M) = D_1(T_L(M)). \qquad (11)$$

Note that this equality is meant as an equality between submaps of $M$, not only as isomorphic maps.

• If there is no admissible loops in $M$, then $D_1(M) = M$.

The interesting point (which needs a two-page proof) in this theorem is that the right member of (11) does not depend on the chosen admissible loop $L$.

## 3.2 Complete decomposition

It is immediate from the definition that every map $M'$ appearing with a non-zero coefficient in $D_1(M)$ has no admissible loops. Thus they are of the following form (drawn on figure 3):

The vertex ⋆ is the extremity of half-edges $h_i(0 \le i \le l)$, including the external one $h_0$, numbered with respect to the cyclic order. For $i \ge 1$, $h_i$ belongs to an edge $e_i$, whose other extremity is $v_i$. Each $v_i$ is in a different connected component $M_i$ (called leg) of $M\{h_1, \dots, h_l\}$. Note that we have only erased the half-edge $h_i$ and not the whole edge $e_i$ so that each $M_i$ keeps an external half-edge.

If we have a family of submaps $M'_i = M_i\{E'_i\}$ of the $M_i$'s we consider the map $\phi_M(M'_1, \dots, M'_l) = M\bigcup\{E'_i\}$ obtained by replacing in $M$ each $M_i$ by $M'_i$.

The outcome of operator $D_1$ is an algebraic sum of maps, which are much more complicated than planar forests. So, in order to write $N(M)$ as an algebraic sum of series associated to minimal factorizations,
<figure><img src="image_4.png" /><figcaption>Fig. 4: Map $\overline{M}$.</figcaption></figure>

we have to iterate such operations.

We want to define decompositions of maps associated to pairs of permutations, so of edge-labeled bicolored maps without external edges. But it is convenient to work on a bigger module: the ring $A_{blm, \le 1}$ of bicolored labeled maps with at most one external half-edge per connected component.

**Definition-Proposition 3.2.1** There exists a unique linear operator

$$D : A_{blm, \le 1} \to A_{blm, \le 1}$$

such that:

1. If $M$ has only one vertex, then $D(M) = M$;

2. If $M$ has more than one connected components $M = \bigcup M_i$, then $D(M) = \bigcup D(M_i)$;

3. If $M$ has only one connected component and no external half-edge, consider its edge $e$ of smallest label. Let $h$ be the half-edge of $e$ of black extremity $b$. We denote by $\overline{M}$ the map obtained by adding one external half-edge of extremity $b$ just after $h$. Then $D(M) = D(\overline{M})$;

4. If $M$ has only one connected component with one half-edge but no admissible loops, we use the notations of the previous paragraph. As the $M_i$ are connected maps with an external half-edge, we can compute $D(M_i)$ (third or fifth case). Then $D(M)$ is given by the formula:

$$D(M) = \phi_M(D(M_1), \dots, D(M_l)),$$

where $\phi_M$ is extended by multilinearity to algebraic sums of submaps of the $M_i$'s.

5. Else, $D(M) = D(D_1(M))$.

Existence and uniqueness of $D$ are obvious. Like $D_1$, the operator $D$ consists in iterating transformations of kind $T_L$, so it leaves $N$ invariant. The image of a map $M$ by $D$ is in the subspace generated by its submaps with the same set of vertices, no isolated vertices and no loops, i.e. its covering forests without trivial trees. Note also that forests are fixed points for $D$ (immediate induction).

**Example 2** We will compute $D(M)$ where $M$ is the map from figure 4 (without the external half-edge). The map $M$ belongs to the third kind, so we have to add an external half-edge as on figure. Now, $\overline{M}$ is a map of the fifth type and we have to compute $D_1(\overline{M})$: this is very easy because the two transformations
<figure><img src="image_5.png" /><figcaption>Fig. 5: Maps involved in the computation of the example.</figcaption></figure>

associated with admissible loops lead to the same sum of submaps which do not contain any admissible loop.

$$ 
\begin{aligned}
D_1(M) &= M\{1\} + M\{2\} - M\{1, 2\} \\
\text{So } D(M) &= D(M\{1\}) + D(M\{2\}) - D(M\{1, 2\})
\end{aligned}
$$

The map $M\{1\}$ is a map of the fourth type with only one leg $M_1$, which is drawn at figure 5.

This map $M_1$ is again of the fourth type (with one leg: the map $M_2$ from figure 5) so we have to compute $D(M_2)$, which is simply $D_1(M_2) = M_2\{5\}$. This implies immediately that $D(M_1) = M_1\{5\}$ and:

$$ D(M\{1\}) = M\{1, 5\}. $$

$$ \text{Similarly, } D(M\{2\}) = M\{2, 3\}. $$

Now we look at the map $M\{1, 2\}$. It has two connected component (we have to apply rule 2): one is a tree and has a trivial image by $D$, the other one $M_3$ has no external half-edge. We have to add one external half-edge to $M_3$ with the third rule and obtain $M_4$. Now, it is clear that $D_1(M_4) = M_4\{3\}$, so one has $D(M\{1, 2\}) = M\{1, 2, 3\}$.

Finally,

$$ D(M) = M\{1, 5\} + M\{2, 3\} - M\{1, 2, 3\}. $$

## 3.3 Signs

In this paragraph, we study the sign of the coefficients in the expression $D(M)$. This is central in the proof of theorem 1.3.2 because we will show that the coefficients of $K'_\mu$ can be written as a sum of coefficients of $D(M)$, for some particular maps $M$.

**Proposition 3.3.1** Let $M' \subset M$ two maps with the same set of vertices and respectively $t_{M'}$ and $t_M$ connected components. The sign of the coefficient of $M'$ in $(-1)^{t_M} D(M)$ is $(-1)^{t_{M'}}$.

**Proof:** Due to the inductive definition of $D$ using $D_1$, it is enough to prove the result for operator $D_1$ in the case where $M$ is a connected ($t_M = 1$) bicolored map with one external half-edge. We proceed by induction over the number of edges in $M\setminus M'$. If $M' = M$, the result is obvious. Note that if $M'$ has a non-zero coefficient in $D_1(M)$, we have necessarily $M\setminus M' = \{e_1, \dots, e_l\}$ where each $e_i$ belongs at least to one admissible loop.

*First case:* There exists an edge $e \in M\setminus M'$ such that $M\{e\}$ has at least one admissible loop. Put $M_1 = M\{e\}$. As we can choose any admissible loop at each step to compute $D_1(M)$, let us choose, whenever it is possible, a loop which does not contain $e$. After transformations with respect to these loops, we get $D_1(M_1) \cup \{e\}$ (that is the sum of maps obtained by adding the edge $e$ to all maps in $D_1(M_1)$). So, one has: $D_1(M) = D_1(D_1(M_1) \cup \{e\})$. The submaps $M''$ of $M_1$ containing $M'$ can be divided in two classes:
* Either $M'' \cup \{e\}$ has the same number $t$ of connected components as $M''$. By induction hypothesis, the sign of the coefficient of $M'' \cup \{e\}$ in $D_1(M_1) \cup \{e\}$ is $(-1)^{t-1}$;

* Or $M'' \cup \{e\}$ has strictly less connected components than $M''$. In this case $\{e\}$ does not belong to any loops of $M'' \cup \{e\}$, so every graph appearing in $D_1(M'' \cup \{e\})$ does contain $\{e\}$. In particular, the coefficient of $M'$ in $D_1(M'' \cup \{e\})$ is zero.

Finally, the coefficient of $M'$ in $D_1(M)$ is the same as in the sum of $D_1(M'' \cup \{e\})$ for $M''$ of the first class. So the result comes from the induction hypothesis applied to $M' \subset M'' \cup \{e\}$ (which can be done because $M'' \cup \{e\}$ has strictly less edges than $M$).

*Second case:* Else, up to a new numbering of edges of $M \setminus M'$, the map $M'$ has $l$ connected components $M'_1, \dots, M'_l$ and, for each $i$, the two extremities of $e_i$ belong to $M'_i$ and $M'_{i+1}$ (convention: $M'_{l+1} = M'_l$).

Choose any admissible loop $L$, it contains all the edges $e_i$. Indeed, if we look at a map of the kind $M'' = M \setminus E'$, with $E' \subset \{e_1, \dots, e_l\}$, all edges of $\{e_1, \dots, e_l\} \setminus E'$ do not belong to any loop of $M''$ and are never erased in the computation of $D_1(M)$. So the only term in $T_L(M)$ which contribute to the coefficient of $M'$ is $(-1)^{l-1}M'$. $\square$

# 4 Coefficients of Kerov's polynomials

## 4.1 End of the proof of main theorem

We use the $D$-invariance of $N$ to write $\Sigma'_\mu$ as an algebraic sum of power series appearing in (3):

$$ \Sigma'_{\mu} = \sum_{\substack{\tau, \bar{\tau} \in S(k) \\ \tau \bar{\tau} = \sigma \\ <\tau, \bar{\tau}> \text{ trans.}}} (-1)^{|C(\tau)|+1} N(D(M^{\tau, \bar{\tau}})); \quad (12) $$

But, thanks to the existence of Kerov's generalized polynomials, one has:

$$ \Sigma'_{\mu} = \sum_{\alpha} \pm \prod_{i=1}^{t_{\alpha}} R_{j_{i}(\alpha)+1}. \quad (13) $$

These two expressions are linked by the following technical (non-easy) result :

**Lemma 4.1.1** If we develop the right member of (13) with the formula (3), we obtain exactly, up to a new ordering of the terms, the right member of (12).

As the forest $F_{j_1, \dots, j_t}$ with $t$ trees with one black vertex and respectively $j_1 - 1, \dots, j_t - 1$ black vertices appear only in the monomials in cumulants $\prod R_{j_i}$ with coefficient $(-1)^{v+t}$ ($v$ is the number of vertices of $F$), one has:

**Proposition 4.1.2** The coefficient of monomial $\prod_{i=1}^t R_{j_i+1}$ in $K'_\mu$ is the coefficient of $F_{j_1, \dots, j_t}$ in

$$ (-1)^{t-1} \sum_{\substack{\tau, \bar{\tau} \in S(K) \\ \tau \bar{\tau} = \sigma, <\tau, \bar{\tau}> \text{trans.} \\ |C(\tau)|=t}} D(M^{\tau, \bar{\tau}}). $$
Together with proposition 3.3.1 and the fact that transitive factorizations have connected associated maps, this ends the proof of the main theorem 1.3.2.

## 4.2 Explicit computations

Proposition 4.1.2 is useful, in some cases, to give an explicit expression or a combinatorial interpretation of coefficients. We can recover the formula for terms of graded degree $k-1$ in $K_k$ (already proved in two different ways by I.P. Goulden and A. Rattan in [GR] and by P. Śniady in [Śn]) and the combinatorial interpretation of coefficients of linear monomials in $\mathbf{R}$ (proved in [Bi3] for $\mu = (k)$ and then in the context of generalized polynomial in [RŚ]). But one can also state new results:

**Theorem 4.2.1 (quadratic coefficients)** Let $k, j, l$ be positive integers, the coefficient of $R_j R_l$ in $K'_\mu$ is the number (respectively half the number if $j=l$) of pairs $(\tau, \varphi)$ which fulfill the following conditions:

* The first element $\tau$ is a permutation in $S(k)$ such that $|C(\tau)| = 2$. The second element $\varphi$ is a bijection $|C(\tau)| \stackrel{\sim}{\to} \{1; 2\}$. So we count some permutations with numbered cycles.

* $\tau^{-1}\sigma$ has $j+l-2$ cycles. ($\sigma$ is a given permutation of type $\mu$.)

* Among these cycles, at least $j$ have an element in common with $\varphi^{-1}(1)$ and at least $l$ with $\varphi^{-1}(2)$.

**Theorem 4.2.2** Let $N(l_1, \dots, l_t; L)$ be the number of solutions of the equation $x_1 + \dots + x_t = L$, fulfilling the condition that, for each $i$, $x_i$ is an integer between 0 and $l_i$. Then, the coefficient of a monomial $\prod_{i=1}^t R_{j_i}$ of graded degree $r+s$ in $K'_{r,s}$ is:

$$ \frac{r \cdot s}{t} |\mathrm{Perm}(\mathbf{j})| N(j_1 - 2, \dots, j_t - 2; r - t), \quad (14) $$

where $\mathrm{Perm}(\mathbf{j})$ is the set of sequences equal to $\mathbf{j}$ up to a permutation ($|\mathrm{Perm}(\mathbf{j})| = \frac{t!}{m_2! \dots m_{k-1}!}$ is the multinomial coefficient of the $m_l$'s, where $m_l$ is the number of $j_i$ equal to $l$).

This is the highest graded degree terms in $K'_{r,s}$. A consequence of this result (together with the term of degree $k-1$ in $K_k$) is the subdominant term for character values on any fixed permutation:

**Corollary 4.2.3** For any $\mu = (k_1, \dots, k_r) \vdash k$, one has:

$$ \begin{aligned} \Sigma_{\mu} = & \prod_{i=1}^{r} R_{k_i+1} + \sum_{i=1}^{r} \left[ \left( \prod_{h \neq i} R_h \right) \left( \sum_{|\mathbf{j}|=i-1} \frac{(k-1)k(k+1)}{24} |\mathrm{Perm}(\mathbf{j})| \prod_{i}^{l(\mathbf{j})} (j_i-1)R_{j_i} \right) \right] \\ & + \sum_{1 \le i_1 < i_2 \le r} \left[ \left( \prod_{h \neq i_1, i_2} R_h \right) \left( \sum_{|\mathbf{j}|=i_1+i_2} \frac{i_1 \cdot i_2}{l(\mathbf{j})} |\mathrm{Perm}(\mathbf{j})| N(j_1-2, \dots, j_{l(\mathbf{j})}-2; i_1-l(\mathbf{j})) \prod_{i=1}^{l(\mathbf{j})} R_{j_i} \right) \right] \\ & + \text{lower graded degree terms.} \end{aligned} $$

**Proof:** In equation (7), the only summands which contain terms of degree $|\mu|+r-2$ are the one indexed by the partition of $[l(\mu)]$ in singletons and those indexed by partitions in one pair and singletons. $\square$
Acknowledgements

The author would like to thank his adviser Philippe Biane for introducing him to the subject, helping him in his researches and reviewing (several times) this paper. He also thanks Piotr Śniady for stimulating discussions.

References

[Bi1] P. Biane, Some properties of crossings and partitions, Discrete Math., **175** (1-3), 41-53 (1997).

[Bi2] P. Biane, *Representations of symmetric groups and free probability*, Advances in Mathematics **138**, 126-181 (1998).

[Bi3] P. Biane, *Characters of symmetric groups and free cumulants*, Asymptotic Combinatorics with Applications to Mathematical Physics, A. Vershik (Ed.), Springer Lecture Notes in Mathematics 1815, 185-200 (2003).

[Bi4] P. Biane, *On the formula of Goulden and Rattan for Kerov polynomials*, Séminaire Lotharingien de Combinatoire, **55**, Art. B55d (2005/06).

[Fé] V. Féray, *Proof of Stanley's conjecture about irreducible character values of the symmetric group*, arXiv preprint math.CO/0612090 (2006), to appear in Annals of combinatorics.

[FŚ] V. Féray and P. Śniady, *Asymptotics of characters of symmetric groups related to Stanley-Féray formula*, arXiv preprint math/0701051 (2007).

[GJ] I.P. Goulden and D.M. Jackson, *The combinatorial relationship between trees, cacti, and certain connection coefficients for the symmetric group*, European J. Combinatorics **13**, 357-365 (1992).

[GR] I.P. Goulden and A. Rattan, *An explicit form for Kerov's character polynomials*, Trans. Amer. Math. Soc. **359**, 3669-3685 (2007).

[Ke] S. Kerov, *The asymptotics of interlacing sequences and the growth of continual Young diagrams*, Journal of Mathematical Science, **80** (3), 1760-1767 (1996).

[Ma] I.G. Macdonald, *Symmetric functions and Hall polynomials*, Oxford Univ. Press, Oxford (1979).

[RŚ] A. Rattan and P. Śniady, *Upper bounds on the characters of the symmetric group for balanced Young diagram and a generalized Frobenius formula*, arXiv preprint math.RT/0610540 (2006).

[Śn] P. Śniady, *Asymptotics of characters of symmetric groups, genus expansion and free probability*, Discrete Math., **306** (7), 624-665 (2006).

[St1] R. Stanley, *Irreducible symmetric group characters of rectangular shape*, Sém. Lotharingien de Combinatoire (electronic) **50**, B50d (2003).

[St2] R. Stanley, *A conjectured combinatorial interpretation of the normalized irreducible character values of the symmetric group*, arXiv preprint math.CO/0606467 (2006).