# Polynomial functions on Young diagrams arising from bipartite graphs

Maciej Dołęga<fnref n="1" /> and Piotr Śniady¹²

**Abstract.** We study the class of functions on the set of (generalized) Young diagrams arising as the number of embeddings of bipartite graphs. We give a criterion for checking when such a function is a polynomial function on Young diagrams (in the sense of Kerov and Olshanski) in terms of combinatorial properties of the corresponding bipartite graphs. Our method involves development of a differential calculus of functions on the set of generalized Young diagrams.

**Résumé.** Nous étudions la classe des fonctions sur l'ensemble des diagrammes de Young (généralisés) qui sont définies comme des nombres d'injections de graphes bipartites. Nous donnons un critère pour savoir si une telle fonction est une fonction polynomiale sur les diagrammes de Young (au sens de Kerov et Olshanski) utilisant les propriétés combinatoires des graphes bipartites correspondants. Notre méthode repose sur le développement d'un calcul différentiel sur les fonctions sur les diagrammes de Young généralisés.

**Keywords:** Polynomial functions on Young diagrams, coloring of bipartite graphs, differential calculus on Young diagrams

The full version of this extended abstract will be published elsewhere.

# 1 Introduction

## 1.1 Prominent examples of polynomial functions on Young diagrams

The character $\chi^\lambda(\pi)$ of the symmetric group is usually considered as a function of the permutation $\pi$, with the Young diagram $\lambda$ fixed. Nevertheless, it was observed by Kerov and Olshanski (1994) that for several problems of the asymptotic representation theory it is convenient to do the opposite: keep the permutation $\pi$ fixed and let the Young diagram $\lambda$ vary. It should be stressed the Young diagram $\lambda$ is arbitrary, in particular there are no restrictions on the number of boxes of $\lambda$. In this way it is possible to study the structure of the series of the symmetric groups $S_1 \subset S_2 \subset \dots$ and their representations in a uniform way. In order for this idea to be successful one has to replace the usual characters $\chi^\lambda(\pi)$ by, so called, *normalized characters* $\Sigma_\pi(\lambda)$, namely for partitions $\pi$, $\lambda$ such that $|\pi| = k$, $|\lambda| = n$ we define

$$ \Sigma_{\pi}(\lambda) = \begin{cases} \frac{n(n-1)\cdots(n-k+1)^{\frac{\chi^{\lambda}(\pi, 1^{n-k})}{\chi^{\lambda}(1^n)}}}{k \text{ factors}} & \text{if } k \le n, \\ 0 & \text{otherwise.} \end{cases} $$

<footnote n="1">¹Instytut Matematyczny, Uniwersytet Wrocławski, Wrocław, Poland</footnote>

<footnote n="2">²Instytut Matematyczny, Polska Akademia Nauk, Warszawa, Poland</footnote>
There are several other interesting examples of functions on the set of Young diagrams which in some sense — which will be specified in Section 1.2 — are similar to the normalized characters; we recall some of them in the following.

Free cumulants $R_k(\lambda)$, introduced by Kerov (2000a) and Biane (2003), are relatively simple functionals of the shape of the Young diagram $\lambda$. Their advantage comes from the fact that the normalized characters can be expressed in terms of free cumulants and that this expression takes a particularly simple form (Biane, 2003).

There are other interesting functionals of the shape of the Young diagram and fundamental functionals of shape, which are defined in Section 2.3, are very simple examples. These functionals are quite useful and powerful in the context of differential calculus on Young diagrams.

Jack symmetric functions (Jack, 1970/1971) are a generalization of Schur functions and are indexed by an additional parameter $\alpha > 0$. They can be used to define Jack characters $\Sigma_{\pi}^{(\alpha)}(\lambda)$ which are a natural generalization of the normalized characters of the symmetric groups. For some special values of $\alpha$ Jack symmetric functions become well-known objects. For example, for $\alpha = 2$ we obtain so-called zonal polynomial which is a zonal spherical function for the Gelfand pairs $(\mathfrak{S}_{2n}, H_n)$, where $H_n$ denotes the hyperoctahedral group. This example has an important meaning in the representation theory for Gelfand pairs. Jack characters are related with $\alpha$-anisotropic Young diagrams which are deformed Young diagrams with respect to the parameter $\alpha$. More precisely, for a Young diagram $\lambda = (\lambda_1, \dots, \lambda_k)$ we can construct an $\alpha$-anisotropic Young diagram $\alpha\lambda$ by rescaling the original diagram in one direction by parameter $\alpha$, i.e. $\alpha\lambda = (\alpha\lambda_1, \dots, \alpha\lambda_k)$. The connection between functions on $\alpha$-anisotropic Young diagrams and Jack polynomials was obtained by Kerov (2000b).

## 1.2 The algebra of polynomial functions on Young diagrams

Kerov and Olshanski (1994) defined the algebra $\mathcal{P}$ of polynomial functions on the set $\mathbb{Y}$ of Young diagrams. This algebra is generated by every example of a family of functions on Young diagrams which we presented in Section 1.1. The problem of how to express an element of one basis in terms of the elements of another basis of this algebra is very fascinating and it is related to Kerov polynomials, Goulden-Rattan polynomials and many other combinatorial objects which are sometimes well-known, but sometimes far away from being satisfactorily understood.

The algebra $\mathcal{P}$ of polynomial functions on $\mathbb{Y}$ turns out to be isomorphic to a subalgebra of the algebra of partial permutations of Ivanov and Kerov (1999). Therefore we can view the elements of $\mathcal{P}$ as (linear combinations of) partial permutations. Since the multiplication of functions on $\mathbb{Y}$ corresponds to convolution of central functions on partial permutations, we see that the algebra $\mathcal{P}$ turns out to be very closely related to the problems of computing connection coefficients and multiplication of conjugacy classes in the symmetric groups.

The algebra $\mathcal{P}$ is canonically isomorphic to the algebra of *shifted symmetric functions*. The algebra of *shifted symmetric functions* is an important object in the symmetric functions theory and the isomorphism with the algebra $\mathcal{P}$ gives some new results in this field due to Okounkov and Olshanski (1998).

## 1.3 Numbers of colorings of bipartite graphs

The set of vertices of a bipartite graph $G$ will always be $V = V_1 \cup V_2$ with the elements of $V_1$ (respectively, $V_2$) referred to as white (respectively, black) vertices.

We consider a coloring $h$ of the white vertices in $V_1$ by columns of the given Young diagram $\lambda$ and of the black vertices in $V_2$ by rows of the given Young diagram $\lambda$. Formally, a coloring is a function
$h: V_1 \sqcup V_2 \to \mathbb{N}$ and we say that this coloring is compatible with a Young diagram $\lambda$ if $(h(v_1), h(v_2)) \in \lambda$ (where $(h(v_1), h(v_2))$ denotes the box placed in $h(v_1)$th column and in $h(v_2)$th row) for each edge $(v_1, v_2)$ of $G$ with $v_1 \in V_1$, $v_2 \in V_2$. Alternatively, a coloring which is compatible with $\lambda$ can be viewed as a function which maps the edges of the bipartite graph to boxes of $\lambda$ with a property that if edges $e_1, e_2$ share a common white (respectively, black) vertex then $h(e_1)$ and $h(e_2)$ are in the same column (respectively, the same row). We can think that such a coloring defines an embedding of a graph $G$ into the Young diagram $\lambda$. We denote by $N_G(\lambda)$ the number of colorings of $G$ which are compatible with $\lambda$ which is the same as the number of embeddings of $G$ into $\lambda$ by the above identification.

## 1.4 Polynomial functions on Young diagrams and bipartite graphs

Suppose that some interesting polynomial function $F \in \mathcal{P}$ is given. It turns out that it is very convenient to write $F$ as a linear combination of the numbers of embeddings $N_G$ for some suitably chosen bipartite graphs $G$:

$$F = \sum_{G} \alpha_{G} N_{G} \qquad (1)$$

which is possible for any polynomial function $F$. This idea was initiated by Féray and Śniady (2011a) who found explicitly such linear combinations for the normalized characters $\Sigma_{\pi}(\lambda)$ and who used them to give new upper bounds on the characters of the symmetric groups. Another application of this idea was given by Dołęga, Féray, and Śniady (2010) who found explicitly the expansion of the normalized character $\Sigma_{\pi}(\lambda)$ in terms of the free cumulants $R_s(\lambda)$; such expansion is called Kerov polynomial (Kerov, 2000a; Biane, 2003).

The above-mentioned two papers concern only the case when $F = \Sigma_{\pi}$ is the normalized character, nevertheless it is not difficult to adapt them to other cases for which the expansion of $F$ into $N_G$ is known. For example, Féray and Śniady (2011b) found also such a representation for the zonal characters and in this way found the Kerov polynomial for the zonal polynomials.

It would be very tempting to follow this path and to generalize these results to other interesting polynomial functions on $\mathbb{Y}$. However, in order to do this we need to overcome the following essential difficulty.

**Problem 1.1** For a given interesting polynomial function $F$ on the set of Young diagrams, how to find explicitly the expansion (1) of $F$ as a linear combination of the numbers of colorings $N_G$?

This problem is too ambitious and too general to be tractable. In this article we will tackle the following, more modest question.

**Problem 1.2** Which linear combinations of the numbers of colorings $N_G$ are polynomial functions on the set of Young diagrams?

Surprisingly, in some cases the answer to this more modest Problem 1.2 can be helpful in finding the answer to the more important Problem 1.1.

## 1.5 How characterization of polynomial functions can be useful?

Jack shifted symmetric functions $J_{\mu}^{(\alpha)}$ with parameter $\alpha$ are indexed by Young diagrams and are characterized (up to a multiplicative constant) by the following conditions:

(i) $J_{\mu}^{(\alpha)}(\mu) \neq 0$ and for each Young diagram $\lambda$ such that $|\lambda| \le |\mu|$ and $\lambda \neq \mu$ we have $J_{\mu}^{(\alpha)}(\lambda) = 0$;
(ii) $J_{\mu}^{(\alpha)}$ is an $\alpha$-anisotropic polynomial function on the set of Young diagrams, i.e. the function $\lambda \mapsto J_{\mu}^{(\alpha)}(\frac{1}{\alpha}\lambda)$ is a polynomial function;

(iii) $J_{\mu}^{(\alpha)}$ has degree equal to $|\mu|$ (regarded as a shifted symmetric function).

The structure on Jack polynomials remains mysterious and there are several open problems concerning them. The most interesting for us are introduced and investigated by Lassalle (2008, 2009).

One possible way to overcome these difficulties is to write Jack shifted symmetric functions in the form

$$J_{\mu}^{(\alpha)}(\lambda) = \sum_{\pi \vdash |\mu|} n_{\pi}^{(\alpha)} \Sigma_{\pi}^{(\alpha)}(\mu) \Sigma_{\pi}^{(\alpha)}(\lambda),$$

where $n_{\pi}^{(\alpha)}$ is some combinatorial factor which is out of scope of the current paper and where $\Sigma_{\pi}^{(\alpha)}$, called Jack character, is an $\alpha$-anisotropic polynomial function on the set of Young diagrams. The problem is therefore reduced to finding the expansion (1) for Jack characters (which is a special case of Problem 1.1). It is tempting to solve this problem by guessing the right form of the expansion (1) and then by proving that so defined $J_{\mu}^{(\alpha)}$ have the required properties.

We expect that verifying a weaker version of condition (i), namely:

(i') For each Young diagram $\lambda$ such that $|\lambda| < |\mu|$ we have $J_{\mu}^{(\alpha)}(\lambda) = 0$

should not be too difficult; sometimes it does not matter if in the definition of $N_G(\lambda)$ we count all embeddings of the graph into the Young diagram or we count only injective embeddings in which each edge of the graph is mapped into a different box of $\lambda$. If this is the case then condition (i') holds trivially if all graphs $G$ over which we sum have exactly $|\mu|$ edges. Also condition (iii) would follow trivially. The true difficulty is to check that condition (ii) is fulfilled which is exactly the special case of Problem 1.2 (up to the small rescaling related to the fact that we are interested now with $\alpha$-anisotropic polynomial functions).

## 1.6 The main result

The main result of this paper is Theorem 5.1 which gives a solution to Problem 1.2 by characterizing the linear combinations of $N_G$ which are polynomial functions on $\mathbb{Y}$ in terms of a combinatorial property of the underlying formal linear combinations of bipartite graphs $G$.

## 1.7 Contents of this article

In this article we shall highlight just the main ideas of the proof of Theorem 5.1 because the whole proof is rather long and technical. In particular we will briefly show the main conceptual ingredients: differential calculus on $\mathbb{Y}$ and derivation of bipartite graphs.

Due to lack of space we were not able to show the full history of the presented results and to give to everybody the proper credits. For more history and bibliographical references we refer to the full version of this article Dołęga and Śniady (2010) which will be published elsewhere.

# 2 Preliminaries

## 2.1 Russian and French convention

We will use two conventions for drawing Young diagrams: the *French* one in the $0xy$ coordinate system and the *Russian* one in the $0zt$ coordinate system (presented on Figure 1). Notice that the graphs in the
<figure><img src="image_1.png" /></figure>

<figure><img src="image_2.png" /><figcaption>Fig. 1: Young diagram (4, 3, 1) shown in the French and Russian conventions. The solid line represents the profile of the Young diagram. The coordinates system (z, t) corresponding to the Russian convention and the coordinate system (x, y) corresponding to the French convention are shown.</figcaption></figure>

Russian convention are created from the graphs in the French convention by rotating counterclockwise by $\frac{\pi}{4}$ and by scaling by a factor $\sqrt{2}$. Alternatively, this can be viewed as choice of two coordinate systems on the plane: $0xy$, corresponding to the French convention, and $0zt$, corresponding to the Russian convention. For a point on the plane we will define its *content* as its z-coordinate.

In the French coordinates will use the plane $\mathbb{R}^2$ equipped with the standard Lebesgue measure, i.e. the area of a unit square with vertices $(x, y)$ such that $x, y \in \{0, 1\}$ is equal to 1. This measure in the Russian coordinates corresponds to a the Lebesgue measure on $\mathbb{R}^2$ multiplied by the factor 2, i.e. i.e. the area of a unit square with vertices $(z, t)$ such that $z, t \in \{0, 1\}$ is equal to 2.

## 2.2 Generalized Young diagrams

We can identify a Young diagram drawn in the Russian convention with its profile, see Figure 1. It is therefore natural to define the set of generalized Young diagrams $\mathcal{Y}$ (in the Russian convention) as the set of functions $\omega : \mathbb{R} \to \mathbb{R}_+$ which fulfill the following two conditions:

* $\omega$ is a Lipschitz function with constant 1, i.e. $|\omega(z_1) - \omega(z_2)| \le |z_1 - z_2|$,

* $\omega(z) = |z|$ if $|z|$ is large enough.

We will define the support of $\omega$ in a natural way:

$$ \text{supp}(\omega) = \overline{\{z \in \mathbb{R} : \omega(z) \neq |z|\}}. $$

## 2.3 Functionals of shape

We define the fundamental functionals of shape $\lambda$ for integers $k \ge 2$

$$ S_k(\lambda) = (k-1) \iint_{(x,y) \in \lambda} (x-y)^{k-2} dx dy = \frac{1}{2}(k-1) \iint_{(z,t) \in \lambda} z^{k-2} dz dt, $$

where the first integral is written in the French and the second in the Russian coordinates. The family $(S_k)_{k \ge 2}$ generates the algebra $\mathcal{P}$ of polynomial functions on Young diagrams (Dołęga, Féray, and Śniady, 2010).
# 3 Differential calculus of functions on Young diagrams

## 3.1 Content-derivatives

Let $F$ be a function on the set of generalized Young diagrams and let $\lambda$ be a generalized Young diagram. We ask how quickly the value of $F(\lambda)$ would change if we change the shape of $\lambda$ by adding infinitesimal boxes with content equal to $z$. In order to answer this informally formulated question we define a derivative of $F$ with respect to content $z$; this definition is inspired by the Gâteaux derivative. We say that

$$ \partial_{C_z} F(\lambda) = f(z) $$

if $f: \mathbb{R} \to \mathbb{R}$ is a continuous function such that for any $\epsilon > 0$ and $C > 0$ there exists $\delta > 0$ such that for any generalized Young diagrams $\omega_1, \omega_2$ supported on $[-C, C]$ such that $\|\omega - \omega_i\|_{L^1} < \delta$ for $i \in \{1, 2\}$

$$ \left| F(\omega_1) - F(\omega_2) - \frac{1}{2} \int_{\mathbb{R}} f(z)(\omega_1(z) - \omega_2(z)) dz \right| \le \epsilon \|\omega_1 - \omega_2\|_{L^1}. \quad (2) $$

The strange constant $\frac{1}{2}$ in the above definition appears because of the fact that we are working with a Russian convention which rescales the length and the height of the Young diagram by a factor $\sqrt{2}$, hence

$$ \text{Area}(\lambda) = \frac{1}{2} \int_{\mathbb{R}} (\omega(z) - |z|) dz. $$

It can be shown using similar methods as in the case of a standard Gâteaux derivative that a content-derivative has the following properties:

(A) If the derivative $\partial_{C_z} F(\lambda)$ exists, then it is unique.

(B) The Leibniz rule holds, i.e. if $F_1, F_2$ are sufficiently smooth functions then

$$ \partial_{C_z} F_1 F_2 = (\partial_{C_z} F_1) F_2 + F_1 \partial_{C_z} F_2. $$

(C) For any integer $k \ge 2$

$$ \partial_{C_z} S_k = (k-1)z^{k-2}. $$

The next proposition shows important properties of derivation of a polynomial function on $\mathbb{Y}$.

**Proposition 3.1** Let $F$ be a polynomial function on $\mathbb{Y}$.

* For any Young diagram $\lambda$ the function $\mathbb{R} \ni z \mapsto \partial_{C_z} F(\lambda)$ is a polynomial.

* For any $z_0 \in \mathbb{R}$ the function $\mathbb{Y} \ni \lambda \mapsto \partial_{C_{z_0}} F(\lambda)$ is a polynomial function on $\mathbb{Y}$.

* For any integer $k \ge 0$ the function $\mathbb{Y} \ni \lambda \mapsto [z^k] \partial_{C_z} F(\lambda)$ is a polynomial function on $\mathbb{Y}$.

**Proof:** By linearity it is enough to prove it for $F = \prod_{1 \le i \le n} S_{k_i}$. Then, thanks to the properties (B) and (C), we have that

$$ \partial_{C_z} F = \sum_{1 \le i \le n} \prod_{1 \le j \le n, j \ne i} S_{k_j} (k_i - 1) z^{k_i - 2}, $$
which is a polynomial in $z$ for fixed $\lambda$, and which is a polynomial function on $\mathbb{Y}$ for fixed $z = z_0$. Moreover $[z^k]\partial_{C_z} F(\lambda)$ is a linear combination of products of $S_{k_i}$, hence it is a polynomial function on $\mathbb{Y}$, which finishes the proof. $\square$

The main result of this paper is that (in some sense) the opposite implication is true as well and thus it characterizes the polynomial functions on $\mathbb{Y}$.

In order to show it we would like to look at the content-derivative of $N_G(\lambda)$, hence it is necessary to extend the domain of the function $N_G$ to the set of generalized Young diagrams. This extension is very natural. Indeed, we consider a coloring $h: V_1 \sqcup V_2 \to \mathbb{R}_+$ and we say that this coloring is compatible with generalized Young diagram $\lambda$ if $(h(v_1), h(v_2)) \in \lambda$ for each edge $(v_1, v_2) \in V_1 \times V_2$ of $G$. If we fix the order of vertices in $V = V_1 \sqcup V_2$, we can think of a coloring $h$ as an element of $\mathbb{R}_+^{|V|}$. Then we define

$$N_G(\lambda) = \mathrm{vol}\{h \in \mathbb{R}_+^{|V|} : h \text{ compatible with } \lambda\}.$$

Notice that this is really an extension, i.e. this function restricted to the set of ordinary Young diagrams is the same as $N_G$ which was defined in Section 1.3.

Just before we finish this section, let us state one more lemma which will be helpful soon and which explains the connection between the usual derivation of a function on the set of Young diagrams when we change the shape of a Young diagram a bit, and the content-derivative of this function.

**Lemma 3.2** Let $\mathbb{R} \ni t \mapsto \lambda_t$ be a sufficiently smooth trajectory in the set of generalized Young diagrams and let $F$ be a sufficiently smooth function on $\mathbb{Y}$. Then

$$\frac{d}{dt} F(\lambda_t) = \int_{\mathbb{R}} \frac{1}{2} \frac{d\omega_t(z)}{dt} \partial_{C_z} F(\lambda_t) dz.$$

**Proof:** This is a simple consequence of equality (2). $\square$

<figure><img src="image_3.png" /></figure>

# 4 Derivatives on bipartite graphs

Let $G$ be a bipartite graph. We denote

$$\partial_z G = \sum_e (G, e)$$

which is a formal sum (formal linear combination) which runs over all edges $e$ of $G$. We will think about the pair $(G, e)$ that it is graph $G$ with one edge $e$ decorated with the symbol $z$. More generally, if $G$ is a linear combination of bipartite graphs, this definition extends by linearity.

If $G$ is a bipartite graph with one edge decorated by the symbol $z$, we define

$$\partial_x G = \sum_f G_{f \equiv z}$$

which is a formal sum which runs over all edges $f \neq z$ which share a common black vertex with the edge $z$. The symbol $G_{f \equiv z}$ denotes the graph $G$ in which the edges $f$ and $z$ are glued together (which means that also the white vertices of $f$ and $z$ are glued together and that from the resulting graph all multiple
edges are replaced by single edges). The edge resulting from gluing $f$ and $z$ will be decorated by $z$. More generally, if $G$ is a linear combination of bipartite graphs, this definition extends by linearity.

We also define

$$ \partial_y G = \sum_f G_{f \equiv z} $$

which is a formal sum which runs over all edges $f \neq z$ which share a common white vertex with the edge $z$.

**Conjecture 4.1** Let $G$ be a linear combination of bipartite graphs with a property that

$$ (\partial_x + \partial_y) \partial_z G = 0. $$

Then for any integer $k \ge 1$

$$ (\partial_x^k - (-\partial_y)^k) \partial_z G = 0. $$

We are able to prove Conjecture 4.1 under some additional assumptions, however we believe it is true in general.

# 5 Characterization of functions arising from bipartite graphs which are polynomial

## 5.1 The main result

**Theorem 5.1** Let $G$ be a linear combination of bipartite graphs such that

$$ (\partial_x^k - (-\partial_y)^k) \partial_z G = 0 \qquad (3) $$

for any integer $k > 0$. Then $\lambda \mapsto N_G^\lambda$ is a polynomial function on the set of Young diagrams.

The main idea of the proof is to find a connection between content-derivative of a function $N_G$ and a combinatorial derivation of the underlying linear combination of bipartite graphs $G$; we present it in the following.

## 5.2 Colorings of bipartite graphs with decorated edges

Let a Young diagram $\lambda$ and a bipartite graph $G$ be given. If an edge of $G$ is decorated by a real number $z$, we decorate its white end by the number $\frac{\omega(z)+z}{2}$ (which is the $x$-coordinate of the point at the profile of $\lambda$ with contents equal to $z$) and we decorate its black end by the number $\frac{\omega(z)-z}{2}$ (which is the $y$-coordinate of the point at the profile of $\lambda$ with contents equal to $z$). If some disjoint edges are decorated by $n$ real numbers $z_1, \dots, z_n$, then we decorate white and black vertices in an analogous way.

For a bipartite graph $G$ with some disjoint edges decorated we define $N_G(\lambda)$, the number of colorings of $\lambda$, as the volume of the set of functions from undecorated vertices to $\mathbb{R}_+$ such that these functions extended by values of decorated vertices are compatible with $\lambda$.

We will use the following lemma:

**Lemma 5.2** Let $(G, z)$ be a bipartite graph with one edge decorated by a real number $z$. Then

$$ \bullet \frac{d}{dz} N_{(G,z)}(\lambda) = \frac{\omega'(z)+1}{2} N_{\partial_x(G,z)}(\lambda) + \frac{\omega'(z)-1}{2} N_{\partial_y(G,z)}(\lambda), $$
<figure><img src="image_4.png" /><figcaption>Fig. 2: Piecewise-affine generalized Young diagram.</figcaption></figure>

$$ \bullet \partial_{C_z} N_G = N_{\partial_z G}. $$

The proof of this lemma is not difficult, but it is quite technical and we omit it.

Using Lemma 5.2, Theorem 4.1, and results from Section 3 one can prove the following lemma:

**Lemma 5.3** Let the assumptions of Theorem 5.1 be fulfilled. Then

$$ \bullet \ z \mapsto N_{\partial_z G}(\lambda) \text{ is a polynomial and} $$

$$ \bullet \ \lambda \mapsto [z^i] N_{\partial_z G}(\lambda) \text{ is a polynomial function on } \mathbb{Y} \text{ for any } i. $$

**Proof:** The main ideas of the proof are the following. In order to show the first property we are looking at $\frac{d^i}{dz^i} N_{\partial_z G}$ and using Lemma 5.2 we can show that $\frac{d^i}{dz^i} N_{\partial_z G} = 0$ for any $i > |V| - 2$. The proof of the second property is going by induction on $i$ and it uses a Lemma 3.2 in a similar way like the proof of Theorem 5.1 below. It is quite technical, so let us stop here. $\square$

## 5.3 Proof of the main result

**Proof of Theorem 5.1:** We can assume without loss of generality that every graph which contributes to $G$ has the same number of vertices, equal to $m$. Indeed, if this is not the case, we can write $G = G_2 + G_3 + \dots$ as a finite sum, where every graph contributing to $G_i$ has $i$ vertices; then clearly (3) is fulfilled for every $G' := G_i$.

Assume that $\lambda$ is a piecewise affine generalized Young diagram such that $|\omega'(z)| < 1$ for any $z$ in the support of $\omega$ (see Figure 2). For any $t \in \mathbb{R}_+$ we define a generalized Young diagram $t\lambda$ which is a dilation of $\lambda$ by $t$. A profile $\tilde{\omega}$ of $t\lambda$ is given by $\tilde{\omega}(s) = t\omega(s/t)$. By Lemma 3.2 we can write:

$$ N_G(\lambda) = \frac{1}{m} \left. \frac{d}{dt} N_G^{t\lambda} \right|_{t=1} = \frac{1}{2m} \int_{\mathbb{R}} \left. \frac{d}{dt} \left( t\omega(z/t) \right) \partial_{C_z} N_G(t\lambda) \right|_{t=1} dz = \\ \frac{1}{2m} \int_{\mathbb{R}} \left( \omega(z) - z\omega'(z) \right) \partial_{C_z} N_G(\lambda) dz. $$
Then, by Lemma 5.2 we have that

$$N_G(\lambda) = \frac{1}{2m} \int_{\mathbb{R}} (\omega(z) - z\omega'(z)) \sum_{0 \le i \le m-2} (i+1)z^i \mathcal{F}_i(\lambda) dz = \\ \frac{1}{2m} \sum_{0 \le i \le m-2} \mathcal{F}_i(\lambda) \int_{\mathbb{R}} (\omega(z) - z\omega'(z))(i+1)z^i dz = \frac{1}{2m} \sum_{0 \le i \le m-2} \mathcal{F}_i(\lambda) S_{i+2}(\lambda),$$

where $\mathcal{F}_i = \frac{1}{i+1}[z^i]N_{\partial_z G}(\lambda)$ is a polynomial function on $\mathbb{Y}$ for each $i$ by Lemma 5.3. It finishes the proof. $\square$

# 6 Applications

## 6.1 Bipartite maps

A labeled (bipartite) graph drawn on a surface will be called a (bipartite) map. If this surface is orientable and its orientation is fixed, then the underlying map is called oriented; otherwise the map is unoriented. We will always assume that the surface is minimal in the sense that after removing the graph from the surface, the latter becomes a collection of disjoint open discs. If we draw an edge of such a graph with a fat pen and then take its boundary, this edge splits into two edge-sides. In the above definition of the map, by 'labeled' we mean that each edge-side is labeled with a number from the set $[2n]$ and each number from this set is used exactly once.

Each bipartite labeled map can be constructed by the following procedure. For a partition $\lambda \vdash n$ we consider a family of $\ell(\lambda)$ bipartite polygons with the number of edges given by partition $2\lambda = (2\lambda_1, \dots, 2\lambda_{\ell(\lambda)})$. Then we label the edges of the polygons by elements of $[2n]$ in such a way that each number is used exactly once. A pair-partition of $[2n]$ is defined as a family $P = \{V_1, \dots, V_n\}$ of disjoint sets called blocks of $P$, each containing exactly two elements and such that $\cup P = [2n]$. For a given pair-partition $P$ we glue together each pair of edges of the polygons which is matched by $P$ in such a way that a white vertex is glued with the other white one, and a black vertex with the other black one.

## 6.2 Normalized and zonal characters

**Theorem 6.1 (Féray and Śniady (2011b))** Let $\Sigma_{\mu}^{(\alpha)}$ denote the Jack character with parameter $\alpha$. Then:

$$\Sigma_{\mu}^{(1)} = \sum_{M} (-1)^{|V_b(M)|} N_M, \qquad (4)$$

where the summation is over all labeled bipartite oriented maps with the face type $\mu$ and

$$\Sigma_{\mu}^{(2)} = \sum_{M} (-2)^{|V_b(M)|} N_M, \qquad (5)$$

where the summation is over all labeled bipartite maps (not necessarily oriented) with the face type $\mu$.

**Proof:** Due to the characterization of a Jack symmetric function which was given in Section 1.5 it suffices to show that the right hand sides of (4) and (5) satisfy conditions (i), (ii), (iii). Due to lack of space, instead of (i) we will show a weaker condition (i').
<figure><img src="image_5.png" /><figcaption>**Fig. 3:** Example of a construction of a map and its subtree ($\tilde{\mathcal{M}}$, $\tilde{T}$) (on the right) from a given map with its subtree ($\mathcal{M}$, $\mathcal{T}$) (on the left), such that $\tilde{\mathcal{M}}/\tilde{T} = \mathcal{M}/\mathcal{T}$. Face type of maps is given by $\mu = (12)$. As pair-partitions we have $\mathcal{M} = \{\{1, 7\}, \{2, 3\}, \{4, 6\}, \{5, 11\}, \{8, 9\}, \{10, 12\}\}$, $\mathcal{T} = \{\{2, 3\}, \{8, 9\}\}$, $\tilde{\mathcal{M}} = \{\{1, 7\}, \{2, 8\}, \{3, 9\}, \{4, 6\}, \{5, 11\}, \{10, 12\}\}$, $\tilde{T} = \{\{2, 8\}, \{3, 9\}\}$.</figcaption></figure>

Definition of $N$ gives us property (iii) immediately. Property (i') can be shown, as it was mentioned in Section 1.5, by proving that if we change functions $N$ on the right hand sides of (4) and (5) by some other functions $\tilde{N}$ which count ‘injective embeddings’, the equalities will still hold. The proof of that will be the same as in Féray and Śniady (2011b), hence we omit it.

The novelty in the current proof is showing the property (ii). First, we notice that

$$ \sum_{\mathcal{M}} (-2)^{|V_b(\mathcal{M})|} N_{\mathcal{M}}(\lambda) = \sum_{\mathcal{M}} (-1)^{|V_b(\mathcal{M})|} N_{\mathcal{M}}(2\lambda). $$

In the following we shall prove that condition (3) is fulfilled. Let us look at $\partial_x^k(\mathcal{M}, z)$ for some bipartite map $\mathcal{M}$ with one decorated edge by $z$. The procedure of derivation with respect to $x$ can be viewed as taking all subtrees of $\mathcal{M}$ which consist of $k + 1$ edges connected by a black vertex and where one edge is decorated by $z$ and collapsing them to one decorated edge. Let us choose such a subtree $\mathcal{T}$. We can do the following procedure with $\mathcal{T}$: we unglue every edges corresponding to $\mathcal{T}$ locally in a way that we create $k$ copies of a black vertex and local orientation of each vertex is preserved; in this way we obtained locally a bipartite $2k + 2$-gon; then we glue it again but in such a way that we glue white vertices together in this $2k + 2$-gon (see Figure 3). We obtained in this way a new bipartite map $\tilde{\mathcal{M}}$, such that $|V_b(\tilde{\mathcal{M}})| = |V_b(\mathcal{M})| + k$ and which contains a subtree $\tilde{T}$ with $k + 1$ edges and one white vertex. Moreover, collapsing of $\mathcal{T}$ in $\tilde{\mathcal{M}}$ to one decorated edge gives us the same bipartite graph as collapsing of $\tilde{T}$ in $\tilde{\mathcal{M}}$ to one decorated edge. We should check that this map has a face type $\mu$, but this is clear from our construction. Of course we can do the same procedure if we start from $\partial_y^k(\mathcal{M}, z)$, because of the symmetry. These two procedures are inverses of each other hence (3) holds true. Applying the Main Theorem 5.1 to our case we obtain the property (ii), which finishes the proof. $\square$
Acknowledgements

Research was supported by the Polish Ministry of Higher Education research grant N N201 364436 for
the years 2009–2012.

References

P. Biane. Characters of symmetric groups and free cumulants. In *Asymptotic combinatorics with applications to mathematical physics* (St. Petersburg, 2001), volume 1815 of *Lecture Notes in Math.*, pages 185–200. Springer, Berlin, 2003.

M. Dołęga and P. Śniady. Polynomial functions on Young diagrams arising from bipartite graphs. In preparation, 2010.

M. Dołęga, V. Féray, and P. Śniady. Explicit combinatorial interpretation of Kerov character polynomials as numbers of permutation factorizations. *Adv. Math.*, 225(1):81–120, 2010.

V. Féray and P. Śniady. Asymptotics of characters of symmetric groups related to Stanley character formula. *Ann. Math.*, 173(2):887–906, 2011a.

V. Féray and P. Śniady. Zonal polynomials via Stanley's coordinates and free cumulants. *Journal of Algebra*, 334:338–373, 2011b.

V. Ivanov and S. Kerov. The algebra of conjugacy classes in symmetric groups, and partial permutations. *Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI)*, 256(Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 3):95–120, 265, 1999. ISSN 0373-2703.

H. Jack. A class of symmetric polynomials with a parameter. *Proc. Roy. Soc. Edinburgh Sect. A*, 69:1–18, 1970/1971. ISSN 0308-2105.

S. Kerov. Talk in Institute Henri Poincaré, Paris, January 2000a.

S. Kerov and G. Olshanski. Polynomial functions on the set of Young diagrams. *C. R. Acad. Sci. Paris Sér. I Math.*, 319(2):121–126, 1994. ISSN 0764-4442.

S. V. Kerov. Anisotropic Young diagrams and Jack symmetric functions. *Funct. Anal. Appl.*, 34:41–51, 2000b.

M. Lassalle. A positivity conjecture for Jack polynomials. *Math. Res. Lett.*, 15(4):661–681, 2008. ISSN 1073-2780.

M. Lassalle. Jack polynomials and free cumulants. *Adv. Math.*, 222(6):2227–2269, 2009. ISSN 0001-8708.

A. Okounkov and G. Olshanski. Shifted Schur functions. II. The binomial formula for characters of classical groups and its applications. In *Kirillov's seminar on representation theory*, volume 181 of *Amer. Math. Soc. Transl. Ser. 2*, pages 245–271. Amer. Math. Soc., Providence, RI, 1998.