Séminaire Lotharingien de Combinatoire 70 (2014), Article B70j

JACK POLYNOMIALS AND ORIENTABILITY GENERATING SERIES OF MAPS

MACIEJ DOŁĘGA, VALENTIN FÉRAY, AND PIOTR ŚNIADY

Abstract. We study Jack characters, which are the coefficients of the power-sum expansion of Jack symmetric functions with a suitable normalization. These quantities have been introduced by Lassalle who formulated some challenging conjectures about them. We conjecture the existence of a weight on non-oriented maps (i.e., graphs drawn on nonoriented surfaces) which allows to express any given Jack character as a weighted sum of some simple functions indexed by maps. We provide a candidate for this weight which gives a positive answer to our conjecture in some, but unfortunately not all, cases. In particular, it gives a positive answer for Jack characters specialized to Young diagrams of rectangular shape. This candidate weight attempts to measure, in a sense, the non-orientability of a given map.

1. Introduction

1.1. Jack polynomials and Macdonald polynomials. Jack [Jac71] introduced a family of symmetric polynomials — which are now known as Jack polynomials J_{π}^{(α)} — indexed by a partition and a deformation parameter α. From the contemporary point of view, probably the main motivation for studying Jack polynomials comes from the fact that they are a special case of the celebrated Macdonald polynomials which “have found applications in special function theory, representation theory, algebraic geometry, group theory, statistics and quantum mechanics” [GR05]. Indeed, some surprising features of Jack polynomials [Sta89] have led in the past to the discovery of Macdonald polynomials [Mac95], and Jack polynomials have been regarded as a relatively easy case [LV95], which later allowed the understanding of the more difficult case of Macdonald polynomials [LV97]. A brief overview of Macdonald polynomials (and their relationship to Jack polynomials) is given in [GR05].

2010 Mathematics Subject Classification. Primary 05E05; Secondary 05C10, 05C30, 20C30 .

Key words and phrases. Jack polynomials, Jack characters, maps, topological aspects of graph theory.

4 4 6 6 2 3 5 7 1 1

Figure 1.1. Example of an oriented map. The map is drawn on a torus: the left side of the square should be glued to the right side, as well as bottom to top, as indicated by the arrows.

Jack polynomials are also interesting in their own right, for instance in the context of Selberg integrals [Kad97] and in theoretical physics [FJMM02, BH08].

1.2. Jack polynomials, Schur polynomials and zonal polynomials. For some special choices of the deformation parameter α, Jack polynomials coincide (up to some simple normalization constants) with some very established families of symmetric polynomials. In particular, the case α = 1 corresponds to Schur polynomials, α = 2 corresponds to zonal polynomials, and α = \frac{1}{2} corresponds to symplectic zonal polynomials; see [Mac95, Chapter 1 and Chapter 7] for more information about these functions. For these special values of the deformation parameter, Jack polynomials are particularly nice because they have some additional structures and features (usually related to algebra and representation theory), and for this reason they are much better understood.

1.3. Jack polynomials and maps. Roughly speaking, a map is a graph drawn on a surface, see Figure 1.1. In this article we will investigate the relationship between the combinatorics of Jack polynomials and the enumeration of maps.

In the special cases of Schur polynomials (α = 1) and zonal polynomials (α = 2 and α = \frac{1}{2}) this relationship is already well-understood. The generic case is much more mysterious and we will be only able to present some partial results.

1.4. Normalized characters. The irreducible character χ^{λ}(π) of the symmetric group is usually considered as a function of the partition π, with the Young diagram λ fixed. It was a brilliant observation of Kerov and Olshanski [KO94] that for several problems in the asymptotic representation theory it is convenient to do the opposite: keep the partition π fixed and let the Young diagram λ vary. It should be stressed that in this approach the Young diagram λ is arbitrary, in particular there are no restrictions on the number of boxes of λ. In this way it is possible to study the structure of the series of the symmetric groups 𝔖_{1} ⊂ 𝔖_{2} ⊂ ⋯ and their representations in a uniform way. This concept is sometimes referred to as dual approach to the characters of the symmetric groups.

In order for this idea to be successful, one has to replace the usual characters χ^{λ}(π) by the normalized characters Ch_{π}(λ). Namely, for a partition π of size k and a Young diagram λ with n boxes we define

(1.1)  Ch_{π}(λ) = \begin{cases}(n)_{k} \frac{χ^{λ}(π∪1^{n−k})}{χ^{λ}(id)}, & if k ≤ n, \\ 0, & otherwise, \end{cases}

whereχ^{λ}(π∪1^{n−k}) is the character of the irreducible representation indexed by λ evaluated at a permutation of cycle-type π ∪ 1^{n−k} and

(n)_{k} := n(n − 1) ⋯ (n − k + 1)

denotes the falling factorial.

This choice of normalization is justified by the fact that the so defined characters Ch_{π} belong to the algebra of polynomial functions on the set of Young diagrams [KO94], which in the last two decades turned out to be essential for several asymptotic and enumerative problems of the representation theory of the symmetric groups [Bia98, IO02, DFŚ10].

1.5. Jack characters. Lassalle [Las08a, Las09] initiated the investigation of a kind of dual approach to Jack polynomials. Roughly speaking, it is the investigation (as a function of λ, with π being fixed) of the coefficient of p_{π,1,1,...,1} in the expansion of the Jack symmetric polynomial J_{λ}^{(α)} in the basis of power-sum symmetric functions. This coefficient, with some appropriate normalization factor given in Section 2.2, will be denoted by Ch_{π}^{(α)}(λ).

This normalization factor is chosen in such a way that in the important special case of the Schur polynomials (α = 1) one recovers the normalized characters Ch_{π}^{(1)} = Ch_{π} given by (1.1), which already proved to have a rich and fascinating structure. The cases of zonal polynomials, symplectic zonal polynomials, and general Jack polynomials give rise to some new quantities for which in [FŚ11b] we coined the names zonal characters Ch_{π}^{(2)}, symplectic zonal characters Ch_{π}^{(1/2)}, and general Jack characters Ch_{π}^{(α)}.

(a)^{\begin{matrix}Π \\ Σ \\ W \\ V \\ 4 \\ 3 \\ 2 \\ 2 \\ 1 \\ 1 \\ 5 \end{matrix}}  \begin{matrix}Σ \\ Π \\ W \\ V \\ a \\ b \\ c \\ α \\ β \\ 3 \\ 2, 5 \\ 1, 4 \end{matrix} ; (b)

Figure 1.2. (a) Example of a bicolored graph (drawn on the torus) and (b) an example of its embedding F into the Young diagram (3, 1); this embedding is given by F (Σ) = α, F (Π) = β, F (V) = a, F (W) = c, F (1) = F (4) = (aβ), F (2) = F (5) = (aα), F (3) = (cα). The white vertices of the graph were labeled by capital Latin letters, the black vertices by capital Greek letters, and the edges by Arabic numbers. The columns of the Young diagram were indexed by small Latin letters, the rows by small Greek letters.

Another motivation for studying Jack characters Ch_{π}^{(α)} comes from the observation that they form a linear basis of the algebra of α-polynomial functions on the set of Young diagrams (which is a simple deformation of the algebra of polynomial functions mentioned above). This fact is far from being trivial and was established by Lassalle [Las08a, Proposition 2].

The main goal of this paper is to understand the combinatorial structure of Jack characters Ch_{π}^{(α)}. In the following we will give more details about this problem.

1.6. Embeddings of bicolored graphs. A bicolored graph G is defined as a bipartite graph together with the choice of the coloring of its vertex set V = V(G); we denote by V_{•} = V_{•}(G) and V_{∘} = V_{∘}(G) the sets of black and white vertices of G, respectively.

An embedding F of a bicolored graph G into a Young diagram λ is a function which maps V_{∘} to the set of columns of λ, maps V_{•} to the set of rows of λ, and maps the edge set E(G) of G to the set of boxes of λ, see Figure 1.2. We also require that an embedding preserves the relation of incidence, i.e., a vertex v ∈ V(G) and an incident edge e ∈ E(G) should be mapped to a row or column F (v) which contains the box F (e).

We denote by N_{G}(λ) the number of such embeddings of G into λ. The quantities N_{G}(λ) were introduced in the paper [FŚ11a], and they proved to be very useful for studying various asymptotic and enumerative problems of the representation theory of the symmetric groups, see [FŚ11a, DFŚ10].

When dealing with Jack polynomials, it will be convenient to consider the following slightly deformed version:

(1.2)  N_{G}^{(α)}(λ) := (\frac{1}{\sqrt{α}})^{|V_{•}(G)|} (\sqrt{α})^{|V_{∘}(G)|} N_{G}(λ).

Note that N_{G}^{(1)}(λ) = N_{G}(λ).

1.7. Stanley formulas. We will recall some formulas that express Jack characters Ch_{π}^{(α)} in terms of functions N_{G}^{(α)} in the special cases where α ∈ \{\frac{1}{2}, 1, 2\}. Formulas of this type are called Stanley formulas after Stanley, who found such a formula for α = 1 as a conjecture [Sta06].

1.7.1. Stanley formula for α = 1 and oriented maps. Roughly speaking, an oriented map M is defined as a bicolored graph drawn on an oriented surface, see Figure 1.1. Since oriented maps are not in the focus of this article, we do not present all necessary definitions and for the details we refer the reader to [FŚ11a].

It has been observed in [FŚ11a] that a certain formula conjectured by Stanley [Sta06] and proved by the second author [Fér10] for the normalized characters of the symmetric groups can be expressed as the sum

(1.3)  Ch_{π}^{(1)}(λ) = Ch_{π}(λ) = (−1)^{ℓ(π)} ∑_{M}(−1)^{|V_{•}(M)|} N_{M}^{(1)}(λ)

over all oriented bicolored maps M with face-type π. Here and throughout the paper, N_{M}^{(α)} denotes the function N^{(α)} indexed by the underlying graph of the map M while ℓ(π) denotes the number of parts of the partition π.

1.7.2. Stanley formula for α ∈ \{2, \frac{1}{2}\} and non-oriented maps. Roughly speaking, a non-oriented map — or, for short, map — is a bicolored graph drawn on a surface. For a precise definition (and the definition of the facetype) we refer the reader to Section 3.2.

In [FŚ11b] it has been proved that

Ch_{π}^{(2)}(λ) = (−1)^{ℓ(π)} ∑_{M}(−1)^{|V_{•}(M)|} · (−\frac{1}{\sqrt{2}})^{|π|+ℓ(π)−|V(M)|} N_{M}^{(2)}(λ), (1.4)

Ch_{π}^{(1/2)}(λ) = (−1)^{ℓ(π)} ∑_{M} (−1)^{|V_{•}(M)|} · (\frac{1}{\sqrt{2}})^{|π|+ℓ(π)−|V(M)|} N_{M}^{(1/2)}(λ), (1.5)

where the sums run over all non-oriented maps M with face-type π.

The notations and the normalizations in [FŚ11b] are a bit different, so in Section 5.1 we make the link between the statements above and the results of [FŚ11b].

1.8. The main conjecture. Based on the special cases above, on the theoretical results of this paper, and some computer exploration, we dare to formulate the following conjecture.

Main Conjecture 1.1. To each non-oriented map M one can associate some weight wt_{M}(γ) such that:

• for every λ and π, we have

(1.6) Ch_{π}^{(α)}(λ) = (−1)^{ℓ(π)} ∑_{M} (−1)^{|V_{•}(G)|} wt_{M} (\frac{1 − α}{\sqrt{α}}) N_{M}^{(α)}(λ),

where the sum runs over all non-oriented maps M with face-type π;

• wt_{M}(γ) is a polynomial in variable γ with non-negative rational coefficients, of degree (at most)

d(M) := 2 · (number of connected components of M) − χ(M),

where

χ(M) := |V(M)| − |E(M)| + |F(M)|

is the Euler characteristic of M. Moreover, the polynomial wt_{M}(γ) is an even (respectively odd) polynomial if and only if the Euler characteristic χ(M) is an even number (respectively an odd number).

Throughout the paper, we shall denote the argument of wt_{M} in (1.6) by

(1.7)  γ = γ(α) := \frac{1 − α}{\sqrt{α}}.

Remark 1.2. Let us explain a bit more the meaning of our conjecture. We know that for each partition π there exists a collection of polynomials c_{G}(γ) indexed by bicolored graphs such that

(1.8)  Ch_{π}^{(α)}(λ) = ∑_{G} c_{G}(γ) N_{G}^{(α)}(λ)

holds true for an arbitrary Young diagram λ — see Proposition 2.3.

Since the functions N_{G}^{(α)}, seen as functions on the set of Young diagrams, are not linearly independent [Fér09, Proposition 2.2.1], the expansion (1.8) is not unique. Also, as there might be several maps which correspond to a given graph, indexing the sum by maps (instead of graphs) gives even more freedom on the coefficients. Therefore our conjecture should be understood as a claim about the existence of a particularly nice expansion of Ch_{π}^{(α)} in terms of the functions N_{M}^{(α)}.

1.9. Our (unsuccessful) candidate for the weight wt_{M}(γ). As we have seen above, the case α = 1 corresponds to a summation over oriented maps (Eq. (1.3)), while the cases α = 2 and α = \frac{1}{2} correspond to a summation over non-oriented maps (Eqs. (1.4), (1.5)) with some simple coefficients which depend only on some general features of the map, such as the number of the vertices. Thus one can expect that the hypothetical weight wt_{M}(γ) should be interpreted as a kind of measure of non-orientability of a given map M.

This notion of measure of non-orientability is not very well defined. For example, one could require that for α = 1 the corresponding coefficient wt_{M}(0) is equal to 1 if M is orientable and zero otherwise; and that for α ∈ \{\frac{1}{2}, 2\} (which corresponds to γ(α) = ±\frac{1}{\sqrt{2}}) the coefficient wt_{M} (±\frac{1}{\sqrt{2}}) takes some fixed value on all (orientable and non-orientable) maps.

In Section 3.9 we will define some quantity mon_{M} = mon_{M}(γ) which attempts to measure the non-orientability of a given map M. Note that mon_{M} depends on γ(α), and thus implicitly on α as well, but we drop this dependence in the notation. Roughly speaking, mon_{M} is defined as follows: we remove the edges of the map M one after another in a random order. For each edge which is to be removed we check the type of this edge (for example, an edge may be twisted if, in some sense, it is a part of a Möbius band). We multiply the factors corresponding to the types of all edges. The quantity mon_{M} is defined as the mean value of this product.

One could complain that this is a weak measure of non-orientability of a map; in particular for α = 1 the corresponding weight mon_{M} does not vanish on non-orientable maps. Nevertheless, as we shall see, this weight mon_{M} gives a positive answer to our Main Conjecture 1.1 in many (but, regretfully, not all!) cases.

1.10. Orientability generating series Ĉh_{π}^{(α)}(λ). We define the orientability generating series as the formula (1.6)from Main Conjecture 1.1in which the hypothetical weight wt_{M} has been substituted by the weight mon_{M} to be defined in Section 3.9:

(1.9)  Ĉh_{π}^{(α)}(λ) := (−1)^{ℓ(π)} ∑_{M} (−1)^{|V_{•}(M)|} mon_{M}(γ) N_{M}^{(α)}(λ),

where the sum runs over all non-oriented maps M with face-type π. Now it is natural to ask the following question.

Question 1.3. Does the weight mon_{M} give a positive answer to Main Conjecture 1.1?

In other words, is it true that for any partition π and any Young diagram λ the corresponding Jack character and the orientability generating series coincide:

(1.10)  Ch_{π}^{(α)}(λ) = Ĉh_{π}^{(α)}(λ)?

Regretfully, the answer to this question is NO: with extensive computer calculations we were able to find some concrete counterexamples, see Section 7 for more details. Nevertheless, as we shall discuss in the following, it seems that the formula (1.9) predicts some properties of Jack characters surprisingly well. For this reason we hope that the investigation of the quantity (1.9) might shed some light on the problem and eventually lead to the correct solution of Main Conjecture 1.1.

For example, the positive answer for Question 1.3holds for the following special cases: π = (n) which consists of a single part for 1 ≤ n ≤ 8, furthermore for π = (2, 2), and π = (3, 2) (the proofs are computer-assisted). Furthermore, Corollary 4.3 shows that the answer for Question 1.3 is positive also for any of these partitions augmented by an arbitrary number of parts equal to 1.

Also, the positive answer for Question 1.3 holds in the special case α ∈ \{2, \frac{1}{2}\}, see Theorem 5.1.

However, in order to present the most interesting and promising type of predictions given by Formula (1.9), we will need the notion of Stanley polynomials, see below.

1.11. Stanley polynomials. If P = (p_{1}, …, p_{ℓ}) and Q = (q_{1}, …, q_{ℓ}) are sequences of non-negative integers such that q_{1} ≥ ⋯ ≥ q_{ℓ}, we consider the multirectangular Young diagram

P × Q := (\underbrace{q_{1}, …, q_{1}}_{p_{1} times}, …, \underbrace{q_{ℓ}, …, q_{ℓ}}_{p_{ℓ} times}).

\begin{matrix}p_{1} \\ q_{1} \\ p_{2} \\ q_{2} \\ p_{3} \\ q_{3} \end{matrix}

Figure 1.3. Multirectangular Young diagram P × Q.

This concept is illustrated in Figure 1.3. Quantities P and Q are referred to as multirectangular coordinates of the Young diagram P × Q.

Stanley [Sta04] proved that the evaluation Ch_{π}^{(1)}(P × Q) of the normalized character of the symmetric group on a multirectangular Young diagram is a polynomial in the variables p_{1}, …, p_{ℓ}, q_{1}, …, q_{ℓ}. This polynomial, referred to as Stanley polynomial, later turned out to be a powerful tool in the context of Kerov polynomials; see [DFŚ10]. In particular, one could argue that instead of viewing the character λ ↦ Ch_{π}^{(1)}(λ) as a function of the Young diagram, it is more convenient to view it as a function

(p_{1}, …, p_{ℓ}, q_{1}, …, q_{ℓ}) ↦ Ch_{π}^{(1)}(P × Q)

of the multirectangular coordinates. The idea of Stanley polynomials has to be a bit adjusted for the framework of Jack characters Ch_{π}^{(α)}; we will discuss the details below.

If c is a number and P = (p_{1}, …, p_{ℓ}), we use the shorthand notation

cP = c(p_{1}, …, p_{ℓ}) = (cp_{1}, …, cp_{ℓ}).

We will be interested in the evaluations of the Jack character

(1.11)  Ch_{π}^{(α)} (\sqrt{α}P × \frac{1}{\sqrt{α}}Q) ,

as well as in analogous evaluations of the orientability generating series

(1.12)  Ĉh_{π}^{(α)} (\sqrt{α}P × \frac{1}{\sqrt{α}}Q)

in rescaled multirectangular coordinates p_{1}, …, p_{ℓ}, q_{1}, …, q_{ℓ}. Note that for the above expressions to make sense we have to assume that

\sqrt{α} p_{1}, …, \sqrt{α} p_{ℓ}, \frac{1}{\sqrt{α}}q_{1}, …, \frac{1}{\sqrt{α}}q_{ℓ}

are non-negative integers such that

\frac{1}{\sqrt{α}}q_{1} ≥ ⋯ ≥ \frac{1}{\sqrt{α}}q_{ℓ}.

We will show (see Lemma 2.4) that (1.11) (as well as (1.12)) can be written uniquely as a polynomial in the indeterminates

(1.13)  p_{1}, …, p_{ℓ}, q_{1}, …, q_{ℓ}, γ.

These polynomials will also be referred to as Stanley polynomials. It is worth pointing out that the indeterminate α is not listed among the indeterminates (1.13).

1.12. Orientability generating series property. As promised, we will discuss now the predictions given by Formula (1.9) in the context of Stanley polynomials.

1.12.1. The definition.

Definition 1.4 (OGS-property). Consider a pair which consists of • a partition π, and

• a monomial

(1.14)  M = p_{1}^{e_{1}} ⋯ p_{ℓ}^{e_{ℓ}} q_{1}^{f_{1}} ⋯ q_{ℓ}^{f_{ℓ}} γ^{g}

in indeterminates (1.13). We say that the pair (π, M) fulfills the Orientability Generating Series property (OGS-property) if the coefficients of the monomial M in the Stanley polynomials for Jack character (1.11) and in the Stanley polynomial for the orientability generating series (1.12) are equal:

(1.15) [M] Ch_{π}^{(α)} (\sqrt{α}P × \frac{1}{\sqrt{α}}Q) = [M] Ĉh_{π}^{(α)} (\sqrt{α}P × \frac{1}{\sqrt{α}}Q) .

The question is: which pairs (π, M) have the OGS-property? There are known examples of pairs which do not have this property (for example M = p_{1}p_{2}p_{3}q_{1}q_{2}q_{3} and π = (9), see Section 7). The positive examples will be discussed in the following.

JACK POLYNOMIALS AND ORIENTABILITY GENERATING SERIES OF MAPS 11

1.12.2. OGS-property and rectangular Young diagrams. Investigation of the normalized characters Ch_{π}(λ) in the case when λ = p × q is a rectangular Young diagram was initiated by Stanley [Sta04] who noticed that they have a particularly simple structure; in particular he showed that Formula (1.3) holds true in this special case.

This line of research was continued by Lassalle [Las08a] who (apart from other results) studied Jack characters Ch_{π}^{(α)}(p×q) on rectangular Young diagrams. In particular, Lassalle found a recurrence relation [Las08a, Eq. (6.2)] fulfilled by such characters; this recurrence relates the values of Jack characters on a fixed rectangular Young diagram p×q, corresponding to various partitions π. This recurrence relation is essential for the current paper; expression (1.9) was formulated by a careful attempt to reverse-engineer the hypothetical hidden combinatorial structure behind Lassalle’s recurrence. In particular, our measure of non-orientability of maps mon_{M} was from the very beginning chosen in such a way that Formula (1.10) from Question 1.3 holds true for an arbitrary rectangular Young diagram λ = p × q. In Section 4 we will discuss these issues and prove the following theorem. Theorem 1.5.

• If λ = p × q is a rectangular Young diagram, then the answer for Question 1.3 is positive; in other words

Ch_{π}^{(α)}(p × q) = Ĉh_{π}^{(α)}(p × q)

holds true for any partition π and any positive integers p and q.

• If a monomial M involves only variables p_{i}, q_{i}, γ for some value of the index i (i.e., M = p_{i}^{e}q_{i}^{f}γ^{g}) and π is an arbitrary partition, then (M, π) has the OGS-property, i.e., Equality (1.15) holds true.

Extensive computer exploration leads us to believe that the following extension of the above theorem holds true as well. Conjecture 1.6.

• The answer for Question 1.3 is positive if λ = (p_{1}, p_{2}) × (q_{1}, q_{2}) is a multirectangular Young diagram consisting of (at most) two rectangles.

• If monomial M involves only variables p_{i}, p_{j}, q_{i}, q_{j}, γ for some choice of the indices i, j (i.e., M = p_{i}^{e_{i}}p_{j}^{e_{j}}q_{i}^{f_{i}}q_{j}^{f_{j}}γ^{g}) and π is an arbitrary partition, then (M, π) has the OGS-property.

1.12.3. OGS-property for top-degree monomials. One can show that Stanley polynomials for both Jack character (1.11) and for the orientability generating series (1.12) are polynomials in indeterminates (1.13) of degree |π| + ℓ(π). When this article was almost finished, the following positive result about the monomials of this maximal degree was announced.

Theorem 1.7 ([Śni14]). Let π be an arbitrary partition and let monomial M of the form (1.14) be of degree

e_{1} + ⋯ + e_{ℓ} + f_{1} + ⋯ + f_{ℓ} + g = |π| + ℓ(π).

Then the pair (M, π) has the OGS-property.

This positive result is an indication that there could be indeed some truth behind our intuitions on the orientability generating series, and it encourages further investigation of the topic.

1.13. Links with other problems.

1.13.1. Lassalle’s conjectures. Our search for some Stanley formula for general Jack characters Ch_{π}^{(α)} has been motivated by two recent conjectures of Lassalle. He conjectured some nice positivity and integrality properties for the coefficients of Ch_{π}^{(α)} expressed in terms of multirectangular coordinates (i.e., the coefficients of Stanley polynomials) [Las08a, Conjectures 1 and 2] and in terms of free cumulants (see Section 2.3 for the definition) [Las09, Conjectures 1.1 and 1.2], respectively. The positivity part in both conjectures would follow from our Main Conjecture 1.1: for multirectangular coordinates we explain the connection in Section 6, while for free cumulants this would follow from the general machinery developed in [DFŚ10].

1.13.2. The b-Conjecture of Goulden and Jackson. In the current paper we investigate the combinatorics of Jack characters related to maps. The study of analogous connections between Jack polynomials and maps is much older. In particular, Goulden and Jackson [GJ96a] formulated a conjecture (called b-Conjecture) which claims, roughly speaking, that the connection coefficients of Jack polynomials can be explained combinatorially as a summation over certain maps with coefficients that should describe nonorientability of a given map. An extensive bibliography on this topic can be found in [LC09].

Although there is no direct link between our problem and the b-Conjec-ture (we are unable to show, for instance, that one implies the other), both problems seem quite close, and we hope that any progress on one of them could give ideas to solve the other.

1.14. Outline of the paper. In Section 2, we define Jack characters. Then, in Section 3, we give formal definitions related to non-oriented maps and define the weight mon_{M}. In Sections Section 4 and 5, we prove that the answer for Question 1.3 is positive for rectangular Young diagrams on the one hand and, on the other hand, for the special choice of the deformation parameter α ∈ \{\frac{1}{2}, 2\}. In Section 6, we explain the link between Main Conjecture 1.1 and the above-mentioned conjectures of Lassalle. Then, finally, in Section 7, we present our numerical exploration and the counterexample.

2. Preliminaries

2.1. Partitions and Young diagrams. A partition π = (π_{1}, …, π_{l}) is defined as a weakly decreasing finite sequence of positive integers. If π_{1} + ⋯ + π_{l} = n we also say that π is a partition of n and denote it by π ⊢ n. We will use the following notations: |π| := π_{1} + ⋯ + π_{l}; furthermore ℓ(π) := l denotes the number of parts of π and

m_{i}(π) := |{k : π_{k} = i}|

denotes the multiplicity of i ≥ 1 in the partition π. When dealing with partitions we will use the shorthand notation

1^{l} := (\underbrace{1, …, 1}_{l times}).

Any partition can be alternatively viewed as a Young diagram. For drawing Young diagrams we use the French convention.

The conjugacy classes of the symmetric group 𝔖_{n} are in one-to-one correspondence with the partitions of n. Thus any partition π ⊢ n can be also viewed as some (arbitrarily chosen) permutation π ∈ 𝔖_{n} with the corresponding cycle decomposition. This identification between partitions and permutations allows us to define characters such as Tr ρ(π), Ch_{π}^{(α)} for π being either a permutation or a partition.

2.2. Jack characters. Jack characters were introduced by Lassalle [Las08a, Las09]; however, we will use a slightly different normalization than the one used in his papers. This new normalization was introduced and motivated in [DF14]. We present it in the following.

Firstly, as there are several of them, we have to fix a normalization of Jack polynomials. In our context it is most convenient to use the functions denoted by J in the book of Macdonald [Mac95, Section VI, Eq. (10.22)]. We expand the Jack polynomial in the basis of power-sum symmetric functions:

J_{λ}^{(α)} = ∑_{\begin{matrix}ρ: \\ |ρ|=|λ| \end{matrix}} θ_{ρ}^{(α)}(λ) p_{ρ};

then we define the Jack character by

(2.1) Ch_{π}^{(α)}(λ) := α^{− \frac{|π|−ℓ(π)}{2}} \binom{|λ| − |π| + m_{1}(π)}{m_{1}(π)} z_{π} θ_{π∪1^{|λ|−|π|}}^{(α)}(λ),

where

z_{π} = π_{1}π_{2} ⋯ m_{1}(π)! m_{2}(π)! · · · .

It turns out that for α = 1 we recover the usual normalized characters (1.1) of the symmetric groups (see [DF14, Sections 1.3 and 1.4]).

2.3. Free cumulants. We now present the notion of the free cumulants of a Young diagram which will be necessary later in some proofs.

Definition 2.1. For a Young diagram λ, we define the sequence of its free cumulants R_{2}^{(1)}(λ), R_{3}^{(1)}(λ), … which are given (for k ≥ 2) by

(2.2)  R_{k}^{(1)}(λ) := (−1) ∑_{T}(−1)^{|V_{•}(T)|} N_{T}^{(1)}(λ),

where the sum runs over bicolored, planted plane trees with k vertices. The formal definition of a planted plane tree will not be necessary for the purposes of this article; we will only need the fact that each free cumulant is a linear combinations of the functions N_{G}^{(1)}.

The usual way of defining the free cumulants of a Young diagram λ is a two-step procedure [Bia98]: it uses Kerov’s transition measure of λ [Ker93] and the notion of free cumulants of a probability measure on the real line [NS06] which originates in Voiculescu’s free probability theory. Our definition has the advantage of being more direct. The equivalence between both definitions has been established by Rattan [Rat08], see also [FŚ11a, Theorem 9].

Definition 2.2. Dealing with Jack polynomials, it is convenient to use anisotropic free cumulants given by

(2.3)  R_{k}^{(α)}(λ) := (−1) ∑_{T} (−1)^{|V_{•}(T)|} N_{T}^{(α)}(λ),

where the sum runs again over bicolored, planted plane trees with k ≥ 2 vertices.

The difference between (2.2) and (2.3) lies in the use of the deformed number of embeddings N_{T}^{(α)} instead of the non-deformed one. The anisotropic free cumulants have been introduced by Lassalle [Las09]. However, the normalization used here is different and corresponds to the one in [DF14] (for details see Section 2.4 below).

2.4. Relationship to Lassalle’s normalization. For the reader’s convenience we provide below the relationship between the quantities used by Lassalle (in boldface) and the ones used by us:

ϑ_{π∪1^{n−|π|}}^{λ}(α) = \binom{|λ| − |π| + m_{1}(π)}{m_{1}(π)} z_{π} θ_{π∪1^{|λ|−|π|}}^{λ}(α),
(2.4)  Ch_{π}^{(α)}(λ) = α^{− \frac{|π|−ℓ(π)}{2}} ϑ_{π∪1^{n−|π|}}^{λ}(α);
R_{k}^{(α)}(λ) = α^{k/2} R_{k}(λ; α).

Our convention has the advantage of being compatible with the symmetry (α, λ) ↔ (α^{−1}, λ′), where λ′ is the transpose diagram of λ (defined, e.g., in [Mac95, Section 1.1]). Namely,

(2.5)  Ch_{π}^{(α)}(λ) = (−1)^{|π|−ℓ(π)} Ch_{π}^{(1/α)}(λ′);
R_{k}^{(α)}(λ) = (−1)^{k}R_{k}^{(1/α)}(λ′).

The first equation is an adaptation of [Mac95, VI, (10.30)] to our notations, while the second follows easily from the definitions.

2.5. Existence of an N_{G}^{(α)}-expansion for Jack characters.

Proposition 2.3. For each partition π, there exists a collection (c_{G}) of polynomials c_{G} ∈ ℚ[γ] indexed by bicolored graphs such that

(2.6)  Ch_{π}^{(α)}(λ) = ∑_{G} c_{G}(γ(α)) N_{G}^{(α)}(λ)

holds true for an arbitrary Young diagram λ.

Proof. Any sum which is in the form given by the right-hand side of (2.6) shall be called an N_{G}^{(α)}-expansion.

By definition (2.3), any anisotropic free cumulant R_{k}^{(α)} admits an N_{G}^{(α)}- expansion. Moreover, any linear combination and any product of some N_{G}^{(α)}-expansions is also an N_{G}^{(α)}-expansion (indeed, it is straightforward to check that N_{G}^{(α)} · N_{G′}^{(α)} = N_{G⊔G′}^{(α)}). Moreover, the constant function equal to γ has an N_{G}^{(α)}-expansion corresponding to the empty bicolored graph ∅:

γ = γ N_{∅}^{(α)}.

Thus we have shown that each element of the algebra generated by the collection of functions on the set of Young diagrams given by

γ, R_{2}^{(α)}, R_{3}^{(α)}, …

has an N_{G}^{(α)}-expansion.

But, by [DF14, Proposition 3.7], the latter algebra contains each Jack character Ch_{π}^{(α)}, which concludes the proof. □

Unfortunately, not much is known about the expansion of the Jack character Ch_{π}^{(α)} in terms of the anisotropic free cumulants. Thus the coefficients c_{G} in (1.8) constructed by the above reasoning are not very explicit. Moreover, let us recall that an N_{G}^{(α)}-expansion — if it exists — is not unique (Remark 1.2), and the expansion given by this proof is definitely not the one we are looking for in Main Conjecture 1.1 (the above proof of Proposition 2.3 gives a sum over forests, while Main Conjecture 1.1 requires that a coefficient of a forest should be independent of α).

2.6. Existence of Stanley polynomials.

Lemma 2.4. For each partition π, both the corresponding Jack character

Ch_{π}^{(α)} (\sqrt{α}P × \frac{1}{\sqrt{α}}Q)

and the orientability generating series

Ĉh_{π}^{(α)} (\sqrt{α}P × \frac{1}{\sqrt{α}}Q)

can be expressed (in a unique way) as a polynomial in the indeterminates (1.13).

Proof. We often viewed γ = γ(α) given by (1.7) as a function of the parameter α. It will be convenient now to reverse the optics; for a given γ ∈ ℝ we define α(γ) as the unique positive solution of the equation

γ = \frac{1 − α}{\sqrt{α}}.

Let us fix the value of an integer ℓ ≥ 1. We say that a function F on the set of Young diagrams has the polynomiality property if the map

(p_{1}, …, p_{ℓ}, q_{1}, …, q_{ℓ}, γ) ↦ F (\sqrt{α(γ)} P × \frac{1}{\sqrt{α(γ)}}Q)

coincides with some polynomial in indeterminates (1.13) (with coefficients in ℚ) on the set

P̃ Q := \{(P, Q, γ) : \sqrt{α(γ)} P × \frac{1}{\sqrt{α(γ)}}Q is a Young diagram\} .

For any bicolored graph G, we claim that the function N_{G}^{(α)} has the polynomiality property. Indeed, a slight variation of [FŚ11b, Lemma 3.9] implies that N_{G}^{(1)}(P ×Q) can be expressed as a polynomial (with non-negative, integer coefficients) in the indeterminates p_{1}, …, p_{ℓ}, q_{1}, …, q_{ℓ} with degree |V_{•}(G)| in the variables P and degree |V_{∘}(G)| in the variables Q. Therefore N_{G}^{(α)}(P × Q) (see (1.2)) is a polynomial in the indeterminates

\frac{1}{\sqrt{α}} p_{1}, …, \frac{1}{\sqrt{α}} p_{ℓ}, \sqrt{α} q_{1}, …, \sqrt{α} q_{ℓ}.

Equivalently, N_{G}^{(α)} has the polynomiality property.

Clearly, any linear combination of the functions N_{G}^{(α)} with coefficients in ℚ[γ], also has the polynomiality property. In particular (by Proposition 2.3

and Definition 1.9, respectively), so do Ch_{π}^{(α)} and Ĉh_{π}^{(α)}.

In order to prove uniqueness, it is enough to show that whenever a polynomial F in indeterminates (1.13) vanishes on the set P̃ Q, then F is identically equal to 0. Consider such a polynomial F and set d to be its degree. Let us fix α_{0} > 0 and denote γ_{0} = \frac{1−α_{0}}{\sqrt{α_{0}}} . We define

S = \{i/\sqrt{α_{0}} : 1 ≤ i ≤ d + 1\},
S_{j} = \{(j(d + 1) + i) · \sqrt{α_{0}} : 1 ≤ i ≤ d + 1\} for 0 ≤ j ≤ ℓ − 1.

Strictly from the definition, we have the following inclusion:

\underbrace{S × ⋯ × S}_{ℓ factors}×S_{ℓ−1} × ⋯ × S_{0} × \{γ_{0}\} ⊂ P̃ Q,

so that F vanishes on this Cartesian product. It is easy to prove (for example, by induction on n, the number of the variables) that, if a polynomial of degree d

f ∈ ℝ[x_{1}, …, x_{n}]

vanishes on a Cartesian product T_{1} × ⋯ × T_{n} ⊂ ℝ^{n}, with |T_{i}| > d (for 1 ≤ i ≤ n), then f is identically equal to 0. Therefore — for any fixed value of γ_{0} — F (P, Q, γ_{0}) is equal to 0 as a polynomial in P and Q. As this holds for any choice of the real number γ_{0}, we conclude that F (P, Q, γ) is equal to 0 as a polynomial in P, Q and γ, as desired. □

3. The measure of non-orientability of maps

3.1. Pairings and polygons. A set-partition of a set S is a collection {I_{1}, …, I_{r}} of pairwise disjoint, non-empty subsets, the union of which is equal to S.

A pairing (or, alternatively, pair-partition) of S is a set-partition into pairs. If s is an element of S and P is a pairing of S, the partner of s in P is defined as the unique element t ∈ S such that {s, t} is a pair of P.

For instance, for any integer n ≥ 1,

P = {{1, 2}, {3, 4}, …, {2n − 1, 2n}}

is a pairing of [2n] (we use the standard notation [n] := {1, …, n}). Note that the existence of a pairing of S clearly implies that |S| is even.

Let us consider now two pairings B, W of the same set S consisting of 2n elements. We consider the following bicolored, edge-labeled graph L(B, W):

• it has n black vertices indexed by the pairs of B and n white vertices indexed by the pairs of W;

• its edges are labeled by the elements of S. The extremities of the edge labeled i are the pair of B containing i and the pair of W containing i.

Note that each vertex has degree 2 and each edge has one white and one black extremity. Besides, if we erase the indices of the vertices, it is easy to recover them from the labels of the edges (the index of a vertex is the set of the two labels of the edges incident to this vertex). Thus, in the following we forget the indices of the vertices and view L(B, W) as an edge-labeled graph.

As every vertex has degree 2, the graph L(B, W) can be seen as a collection of polygons. Moreover, because of the proper bicoloration of the vertices, each polygon has an even length. Let 2ℓ_{1} ≥ 2ℓ_{2} ≥ ⋯ be the ordered lengths of these polygons. The partition (ℓ_{1}, ℓ_{2}, …) is called the type of L(B, W) or the type of the couple (B, W).

Special role will be played by the polygons having exactly 2 edges. Such a polygon will be referred to as bigon.

Example 3.1. For partitions

B = {{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}, {A, B}, {C, D}},
W = {{2, 3}, {4, 5}, {6, 7}, {8, 9}, {10, 1}, {B, C}, {D, A}},

the corresponding polygons L(B, W) are shown in Figure 3.1.

Definition 3.2. Let s_{1} and s_{2} be two elements of S that belong to the same polygon of L(P_{1}, P_{2}). Fix an arbitrary orientation of this polygon. Then, one can consider the number of elements of S between s_{1} in s_{2} in the polygon. We say that s_{1} and s_{2} are in an even (respectively odd) position if this number is even (respectively odd). As each polygon has an even size, this definition does not depend on the choice of the orientation. For example, in Example 3.1 the elements 4 and 9 are in an even position, while the elements 1 and 3 are in an odd position.

3.2. Non-oriented maps. The central combinatorial object in this paper is the following.

\begin{matrix}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ A \\ B \\ C \\ D \end{matrix}

Figure 3.1. Polygons obtained from the couple of pairings from Example 3.1.

4 9 ; \begin{matrix}5 \\ D \end{matrix} ; \begin{matrix}6 \\ C \end{matrix} ; \begin{matrix}7 \\ B \end{matrix} ; \begin{matrix}8 \\ A \end{matrix} ; {10 \atop 2} ; {2 \atop 10} ; 1 3

Figure 3.2. Example of a non-oriented map drawn on the projective plane. The left side of the square should be glued with a twist to the right side, as well as bottom to top (also with a twist), as indicated by arrows. This map has been obtained by gluing the edge-sides of the polygon from Figure 3.1 according to the pair-partition given by Eq. (3.1).

Definition 3.3. An (unoriented) map is a triple M = (B, W, E) of pairings of the same set S.

The terminology comes from the fact that it is possible to represent such a triple of pair-partitions as a bicolored graph embedded in a non-oriented (and possibly non-connected) surface. Let us explain how this works.

First, we consider the union of the polygons L(B, W) defined in Section 3.1. The edges of these polygons, that is the elements of the set S, are called edge-sides.

We consider the union of the interiors of these polygons as a (possibly disconnected) surface with a boundary. If we consider two edge-sides, we can glue them: that means that we identify with each other their white extremities, their black extremities, and the edge-sides themselves.

For any pair in the pairing E, we glue the two corresponding edge-sides. In this way we obtain a (possibly disconnected, possibly non-orientable) surface Σ without boundary. After the gluing, the edges of the polygons form a bicolored graph G embedded in the surface. For instance, with the pairings B and W from Example 3.1 and

(3.1) E = {{1, 3}, {2, 10}, {4, 9}, {5, D}, {6, C}, {7, B}, {8, A}},

we get the graph from Figure 3.2 embedded in the projective plane.

In general, the graph G has as many connected components as the surface Σ. Besides, the connected components of Σ \ G correspond to the interiors of the collection of polygons we are starting from, and, thus, they are homeomorphic to open discs. These connected components are called faces.

This makes the link with the more common definition of maps: usually, a (non-oriented, bicolored) map is defined as a (bicolored) connected graph G embedded in a (non-oriented) surface Σ in such a way that each connected component of Σ \G is homeomorphic to an open disc. It should be stressed that with our definition — contrary to the traditional convention — we do not require the map to be connected.

Definition 3.4. Let M = (B, W, E) be a map.

• The elements of B (respectively W) are called black (respectively white) corners.

• The elements of E are called edges; we use the notation E(M) for the set of edges of a map (that is the third element of the triple defining the map).

• The polygons L(B, W) corresponding to the couple of pairings (B, W) are called faces; the set of faces will be denoted by F(M). The face-type of the map is the type of the couple (B, W), as defined in Section 3.1.

• The polygons L(B, E) (respectively L(W, E)) of the couple of pairings (B, E) (respectively (W, E)) are called black vertices (respectively white vertices); their set is denoted by V_{•}(M) (respectively V_{∘}(M)).

• A leaf is a vertex of M of degree 1, that is a bigon of L(B, E) or L(W, E). In other terms, a leaf is a pair of edge-sides which belongs to both E and B or which belongs to both E and W.

• The connected components of the map M correspond to the connected components of the graph G constructed above. Equivalently, they are the equivalence classes of the transitive closure of the relation: x ∼ y if x is the partner of y in E, B or W.

Note that our maps have labeled edge-sides, and each element of S is used exactly once as a label.

The pairing B (respectively W) indicates which edge-sides share the same corner around a black (respectively white) vertex. This explains the names of these pairings.

This encoding of (non-oriented) maps by triples of pairings is of course not new. It can for instance be found in [GJ96b]; the presentation in that paper is nevertheless a bit different as the authors consider there connected monochromatic maps.

3.3. Ribbon graphs. For the purposes of the current paper it is sometimes convenient to represent a map as a ribbon graph (see Figure 3.4) as follows: each vertex is represented as a small disc, and each edge is represented by a thin ribbon connecting two discs in a way that a walk along the boundary of the ribbons corresponds to the walk along the boundary of the faces of a given map.

3.4. Summation over maps with a specified face-type. Summations over maps with a specified face-type (such as in Equations (1.4), (1.5) and (1.9)) should be understood as follows: we fix a couple of pairings (B, W) of type π and consider all pairings E of the same ground set; we sum over the resulting collection of maps (B, W, E). The set of maps with a specified face-type should be understood in an analogous way.

3.5. Three kinds of edges. Let a map M with some selected edge E = {s_{1}, s_{2}} be given. We distinguish three cases (a schematic description and an example of each case are given in Figures 3.5 and 3.6):

• Both edge-sides s_{1} and s_{2} belong to the same face F and are in an

even position (see Definition 3.2).

Graphically, this means that if we travel along the boundary of the face F then we visit the edge E twice and the directions in which we travel twice along the edge E are opposite, see Figure 3.6a.

In this case the edge E is called straight, and we associate to it the weight

mon_{M,E} := 1.

2 4 1 5 4 2 3 6 3 6

Figure 3.3. Example of a map drawn on the Klein bottle: the left-hand side of the square should be glued to the right-hand side (without a twist) and the top side should be glued to the bottom side (with a twist), as indicated by the arrows.

3 6 1 5 4 2

Figure 3.4. The map from Figure 3.3 drawn as a ribbon graph.

• Both edge-sides s_{1} and s_{2} belong to the same face F and are in an

odd position.

Graphically, this means that if we travel along the boundary of the face F, we visit the edge E twice and the directions in which we travel twice along the edge E are the same, see Figure 3.6b.

In this case the edge E is called twisted, and we associate to it the weight

mon_{M,E} := γ = \frac{1 − α}{\sqrt{α}}.

4 9 ; \begin{matrix}5 \\ D \end{matrix} ; \begin{matrix}6 \\ C \end{matrix} ; \begin{matrix}7 \\ B \end{matrix} ; \begin{matrix}8 \\ A \end{matrix} ; {10 \atop 2} ; {2 \atop 10} ; 1 3

Figure 3.5. The non-oriented map from Figure 3.2. On the boundary of each face some arbitrary orientation was chosen, as indicated by the arrows. The edge {4, 9} is an example of a straight edge, the edge {1, 3} is an example of a twisted edge, the edge {6, C} is an example of an interface edge.

(a)  (b)  (c)

Figure 3.6. Three possible kinds of edges in a map (see Figure 3.5): (a) straight edge: both edge-sides of the edge belong to the same face and have opposite orientations, (b) twisted edge: both edge-sides of the edge belong to the same face and have the same orientation, (c) interface edge: the edge-sides of the edge belong to two different faces; their orientations are not important. In all three cases the colors of the vertices are not important.

• Edge-sides s_{1} and s_{2} belong to different faces of the map, see Fig-

ure 3.6c.

In this case the edge E is called interface and we associate to it the weight

mon_{M,E} := \frac{1}{2}.

3.6. Removal of edges. Let P be a pairing of a set S and s_{1}, s_{2} be two distinct elements of S. We define a pairing P_{{s_{1},s_{2}}} of the set S \ {s_{1}, s_{2}} as follows:

• if {s_{1}, s_{2}} is a pair of P, then

P_{{s_{1},s_{2}}} := P \ {{s_{1}, s_{2}}};

• otherwise, consider the partners t_{1} and t_{2} of s_{1} and s_{2}, respectively. The elements s_{1}, s_{2}, t_{1}, t_{2} are all distinct. We define

P_{{s_{1},s_{2}}} := (P \ {{s_{1}, t_{1}}, {s_{2}, t_{2}}}) ∪ {t_{1}, t_{2}}.

In other words, we remove the two pairs containing s_{1} or s_{2}, and we match together the two unmatched elements of S \ {s_{1}, s_{2}}.

Let M = (B, W, E) be a map and E ∈ E be an edge of M. Then we define M \ {E} (or, shortly, M \ E) as the triple

M \ {E} = M \ E := (B_{E}, W_{E}, E_{E}),

which consists of the three original pairings with the edge E removed.

Graphically, this corresponds to the removal of the edge E from the map M. If one extremity (or both extremities) of this edge is a leaf (are leaves), we also remove this vertex (both vertices). Note that a removal of an edge might drastically change the topology of the surface on which the map is drawn; for this reason it might be more convenient to use the graphical representation of a map as a ribbon graph (see Section 3.3) because the effect of an edge removal from a map in this framework is much simpler; namely, we just remove the appropriate edge from the corresponding ribbon graph.

Lemma 3.5. Let P be a pairing of a set S and s_{1}, s_{2}, s_{3}, s_{4} be four distinct elements of S. Then

(P_{{s_{1},s_{2}}})_{{s_{3},s_{4}}} = (P_{{s_{3},s_{4}}})_{{s_{1},s_{2}}} .

Proof. This can be verified by an easy case-by-case analysis. □

The above lemma implies that for any two distinct edges E_{1}, E_{2} of a map M, one has

(M \ E_{1}) \ E_{2} = (M \ E_{2}) \ E_{1},

which allows one to define the map

M \ {E_{1}, …, E_{i}} := ((M \ E_{1}) \ ⋯) \ E_{i}

for an arbitrary subset {E_{1}, …, E_{i}} ⊆ E(M) of the edges of M by an iterative procedure. The fact that the above object is well-defined (i.e., it does not depend on the choice of the order of the edges E_{1}, …, E_{i}) can be also easily justified in a more intuitive way by referring to the ribbon graphs.

3.7. Effect of an edge removal on the faces. Let E = {s_{1}, s_{2}} be one of the edges of the map M. In the following we will investigate the faces of the map M \ E, i.e., the polygons associated to (B_{E}, W_{E}).

3.7.1. Removal of a straight edge. Suppose that E is a straight edge of the map M. By definition, this means that the two edge-sides s_{1} and s_{2} of E belong to the same face F of M. Moreover, if we fix some orientation on the face F, there is an even number, let us say 2i, of the edge-sides between s_{1} and s_{2} in F. With the other orientation there would also be an even number, let us say 2j, of the edge-sides between s_{1} and s_{2} in F. In particular, the face F consists of 2i + 2j + 2 edge-sides. When we remove the edge E, the face F is split into two faces F_{1} and F_{2} which consist of 2i and 2j edge-sides, respectively (in the degenerate case when i or j is equal to 0, the corresponding face does not exist).

This can be easily seen graphically, see Figure 3.7. This figure, and the similar ones hereafter, should be understood as follows.

• We represent in the figures only the polygon(s) containing the edgesides s_{1} and s_{2}; on the left-hand side in the map M and on the righthand side in the map M \ E. The other polygons are not modified by the edge removal.

• The edge-sides which are to be removed, namely s_{1} and s_{2}, are indicated by thick dashed lines.

• For improved readability, the edge-side labels are placed outside of the face. For i ∈ {1, 2} we denote by t_{i}^{B} the partner of s_{i} in B and by t_{i}^{W} the partner of s_{i} in W.

• Consider the black (respectively white) extremity of the edge E = {s_{1}, s_{2}} in the map M. This vertex of M corresponds to the two black (respectively white) vertices of the polygons, namely to the black (respectively white) extremities of the edge-sides s_{1} and s_{2}; note that in a degenerate case these two extremities might coincide. These two black (respectively white) vertices are decorated on the left-hand side of our figures with a square shape (respectively with a diamond shape). After removal of the edge E these two vertices are glued together into a single black (respectively white) vertex which on the right-hand side of our figures is also decorated with the same square shape (respectively diamond shape).

t_{2}^{B} s_{2} t_{2}^{W} t_{1}^{W} s_{1} t_{1}^{B}

2j edges between s_{1} and s_{2} 2i edges between s_{2} and s_{1} removal of a straight edge

t_{2}^{B} t_{1}^{B}

2j edges in total

t_{2}^{W} t_{1}^{W}

2i edges in total

Figure 3.7. The impact on the faces of a removal of a straight edge.

3.7.2. Topological viewpoint on removal of an edge. In order to give some topological intuition to the reader, we shall describe now and in the following (Sections 3.7.3, 3.7.5 and 3.7.7) the effect on the surface of a removal of an edge in each of the three cases. As all the proofs in this paper are done rigorously with the “set theoretical point of view of maps” (Definitions 3.3 and 3.4, etc.), we permit ourselves to stay a bit informal in these topological considerations. For background on non-orientable surfaces, we refer to [LC09, Section 2.1] and the references therein.

We denote by Σ (respectively Σ_{e}) the surface on which the map M (respectively M \ E) is naturally embedded; see Section 3.2. We also denote by G_{M} ⊂ Σ (respectively by G_{M\E} ⊂ Σ_{e}) the graph associated to the map M (respectively to the map M \ E), viewed as a subset of the surface Σ (respectively Σ_{e}). Furthermore, G_{M} \ E ⊂ Σ denotes the graph G_{M} with the edge E removed.

We shall compare:

(S1) the connected components of Σ \ G_{M}, i.e., the faces of the map M, (S2) the connected components of Σ \ (G_{M} \ E), (S3) the connected components of Σ_{e} \(G_{M\E}), i.e., the faces of the map

M \ E. Note that, by definition, each connected component in (S1) and (S3) is homeomorphic to an open disc, while a priori some connected components in (S2) might not be homeomorphic to a disc. If this is indeed the case, then the surface Σ does not fulfill the defining property of the surface Σ_{e} and thus Σ ≠ Σ_{e}.

t_{2}^{B} s_{2} t_{2}^{W} t_{1}^{B} s_{1} t_{1}^{W}

2r edges in total removal of a twisted edge

t_{2}^{B} t_{1}^{B} t_{2}^{W} t_{1}^{W}

2(r − 1) edges in total

Figure 3.8. The impact on the faces of a removal of a twisted edge.

3.7.3. Removal of a straight edge — topological viewpoint. We now come back from the general considerations to the special case when the edge E is a straight edge of the map M. The edge-sides s_{1} and s_{2} of E lie on the border of the same face F (i.e., on the border of the same connected component considered in (S1)), which — by definition — is homeomorphic to an open disc. The parity condition on the relative position of the edgesides s_{1} and s_{2} in F implies that the situation illustrated in Figure 3.6a occurs. Thus, if we erase the edge E and consider the corresponding surface Σ\(G_{M} \E), the face F becomes homeomorphic to an annulus, i.e., the set {z ∈ ℂ : 1 < |z| < 2}. In other terms, one of the components in (S2) is an annulus (and all the other components are homeomorphic to an open disc). In order to get the surface Σ_{e}, we must replace this annulus by two disjoint open discs (both objects have the same border) which will be the elements of (S3). This is in accordance with the fact that the face F of M is split in M \ E into a pair of faces.

In the other direction, in order to transform Σ_{e} into Σ, one has to take two disjoint open discs lying on the surface Σ_{e} and replace them by an annulus, which corresponds to adding a handle to the surface.

3.7.4. Removal of a twisted edge. Suppose E is a twisted edge of the map M. By definition, this means that the two edge-sides s_{1}, s_{2} of E belong to the same face F of the map M and are in an odd position. Let us denote the number of the edge-sides of the face F by 2r. Then, after removal of the edge E, the face F is replaced by a face with 2(r − 1) edge-sides; see Figure 3.8. The other faces are not modified.

3.7.5. Removal of a twisted edge — topological viewpoint. Topologically, a removal of a twisted edge has the following effect. Consider the map M embedded in its surface Σ. Again, both edge-sides s_{1} and s_{2} of E are

t_{1}^{W} s_{1} t_{1}^{B}

2r edges in total

t_{2}^{B} s_{2} t_{2}^{W}

2s edges in total removal of an interface edge

t_{1}^{B} t_{2}^{B} t_{2}^{W} t_{1}^{W}

2(r + s − 1) edges in total

Figure 3.9. The impact on the faces of an interface edge removal.

assumed to lie on the same face F of M. However, now the situation illustrated in Figure 3.6b occurs and, when we remove the edge E, the face F becomes homeomorphic to a Möbius strip; this Möbius strip, denoted by F′, is one of the connected components in (S2). As the border of a Möbius strip is homeomorphic to a circle, one can remove F′ from Σ and replace it by a disk; this disk will be one of the elements of (S3). In this way we obtain a surface Σ′ on which G_{M} \ E is embedded in such a way that each connected component of Σ′ \ (G_{M} \ E) is homeomorphic to an open disk. This is the defining property of Σ_{e}, thus Σ_{e} = Σ′.

Conversely, Σ is obtained from Σ_{e} by replacing a disk by a Möbius strip or, in other words, by adding a cross-cap.

3.7.6. Removal of an interface edge. Suppose E is an interface edge of M. By definition, this means that the two edge-sides s_{1}, s_{2} of E belong to different faces F_{1} and F_{2} of M. Let us denote by 2r and 2s the number of the edge-sides of the face F_{1} and F_{2}, respectively. Then after removal of the edge E, the faces F_{1} and F_{2} are replaced by a single new face with 2(r + s − 1) edge-sides; see Figure 3.9. The other faces are not modified.

3.7.7. Removal of an interface edge — topological viewpoint. Topologically, a removal of an interface edge is very simple. Indeed, when we erase the edge E, the two faces F_{1} and F_{2} adjacent to E in M are merged into a single connected component in (S2) which is homeomorphic to an open disc. So the condition that components of the surface without the graph must be homeomorphic to open disks is not violated and one can simply take Σ_{e} = Σ as the surface on which G_{M} \ E = G_{M\E} is drawn.

3.8. Weight associated to a map with a history. Let M be a map and let some linear order ≺ on its edges be given. This linear order will be called history.

Let E_{1} ≺ ⋯ ≺ E_{n} be the edges of M, listed according to the linear order ≺. We set M_{i} = M \ {E_{1}, …, E_{i}} and define

(3.2)  mon_{M,≺} := ∏_{0≤i≤n−1} mon_{M_{i},E_{i+1}} .

(Recall that the quantity mon_{M,E} appearing on the right-hand side was defined in Section 3.5.) This product mon_{M,≺} can be interpreted as follows: from the map M we remove (one by one) all the edges, in the order specified by the history. For each edge which is about to be removed we consider its weight relative to the current map; finally we multiply all weights.

Please note that the type of a given edge (i.e., straight versus twisted versus interface) might change in the process of removing edges and the weight mon_{M,≺} usually depends on the choice of the history ≺.

3.9. Measure of non-orientability of a map. Let M be a map with n edges. We define

(3.3)  mon_{M} := \frac{1}{n!} ∑_{≺} mon_{M,≺} .

This quantity can be interpreted as the mean value of the weight associated to the map M equipped with a randomly selected history (with all histories having equal probability). This is the central quantity for the current paper. We call it the measure of non-orientability of the map M.

Example 3.6. We consider the map M shown in Figure 3.3. For calculations involving removal of edges it is more convenient to represent this map as a ribbon graph, see Figure 3.4. For the history {3, 6} ≺ {1, 5} ≺ {2, 4} the corresponding weight is equal to mon_{M,≺} = 1 · \frac{1}{2} · 1, while for the history {1, 5} ≺ {3, 6} ≺ {2, 4} the corresponding weight is equal to mon_{M,≺} = γ · γ · 1. The other histories are analogous to these two cases; finally

mon_{M} = \frac{\overbrace{1 · \frac{1}{2} · 1 + 1 · \frac{1}{2} · 1}^{2 summands} + \overbrace{γ · γ · 1 + ⋯ + γ · γ · 1}^{4 summands}}{6}.

Lemma 3.7. Let M be a map. Then mon_{M} is a polynomial in the variable γ of degree (at most)

d(M) := 2 · (number of connected components of M) − χ(M),

where

χ(M) := |V(M)| − |E(M)| + |F(M)|

is the Euler characteristic of M.

The polynomial mon_{M}(γ) is an even (respectively odd) polynomial if and only if the Euler characteristic χ(M) is an even number (respectively an odd number).

Before we give the proof, notice that, if M is a connected map, then \frac{1}{2}d(M) has a natural interpretation as the Euler genus of the surface on which M is drawn. Moreover, if its underlying surface is orientable, then the map cannot have any twisted edges, and thus mon_{M}(γ) does not depend on γ. Hence the degree of the polynomial mon_{M}(γ) satisfies the same bound as some invariants defined by Brown and Jackson [BJ07, Lemma 3.3] and La Croix [LC09, Theorem 4.4].

Proof of Lemma 3.7. We claim that for an arbitrary map M and its edge E:

(A) mon_{M,E} is a polynomial in γ of degree (at most) d(M)−d(M \E); (B) mon_{M,E} is an even (respectively odd) polynomial if and only if

d(M) − d(M \ E) is an even number (respectively an odd number).

Indeed, this statement follows by a careful investigation of each of the three cases considered in Section 3.5 (cases when at least one of the endpoints of E has degree 1 must be considered separately). We present the details in the following.

• Assume that both extremities of E are leaves. Then E is clearly a straight edge, so mon_{M,E} = 1. But M \E has two vertices less, one edge less, one face less, and one connected component less than M. So d(M \ E) = d(M), and the claim holds in this case.

• Assume that exactly one extremity of E is a leaf. Then E is clearly a straight edge, so mon_{M,E} = 1. But M \E has one vertex less, one edge less, and the same number of faces and connected components as M. So d(M \ E) = d(M), and the claim holds in this case.

• Assume that E is straight, but none of its extremities is a leaf. Recall that mon_{M,E} = 1 in this case. But M \ E has one edge less and one more face (see Section 3.7.1) than M. The number of vertices is unchanged, while the number of connected components can be constant or increase by 1. In the first case, d(M \ E) = d(M) − 2, and in the second d(M \E) = d(M). In both cases our claim holds.

• Assume that E is twisted. In this case mon_{M,E} = γ. Furthermore, maps M and M \ E have the same number of connected components, the same number of faces, and the same number of vertices (see Section 3.7.4). However, M \ E has one edge less than M. Thus d(M \ E) = d(M) − 1, and our claim holds in this case.

• Assume that E is an interface edge. In this case mon_{M,E} = \frac{1}{2}. Furthermore, maps M and M \ E have the same number of connected components and the same number of vertices. However, the number of faces decreases by 1 (see Section 3.7.6) as well as the number of edges. Thus d(M \ E) = d(M), and our claim holds in this case.

We apply the above claims (A)and (B) to each factor on the right-hand side of (3.2); as the sum of the degrees of the factors is a telescoping sum, it follows that the statement of the lemma holds true if the polynomial mon_{M} is replaced by mon_{M,≺}, where ≺ is an arbitrary history. The latter result finishes the proof by taking the average over ≺. □

Remark 3.8. The above case-by-case analysis can be understood easily from the topological point of view, at least when the edge removal does not disconnect the graph. Indeed, a removal of a straight (respectively twisted or interface) edge increases the Euler characteristic of the surface by 2 (respectively by 1 or 0), see Sections 3.7.3, 3.7.5 and 3.7.7. It also increases the degree in γ by 0 (respectively 1 or 0). In all cases, the degree in γ increases at most as much as the Euler characteristic of the surface decreases, which explains our lemma.

4. Rectangular Young diagrams and Lassalle’s recurrence

The main result of this section is the following, which constitutes the first part of Theorem 1.5 (the proof of the remaining part of Theorem 1.5 is postponed until Section 4.5).

Theorem 4.1. For any rectangular Young diagram

λ = p × q = (\underbrace{q, …, q}_{p times}),

and for an arbitrary partition π and parameter α > 0, the answer for Question 1.3 is positive, i.e.,

(4.1)  Ch_{π}^{(α)}(p × q) = Ĉh_{π}^{(α)}(p × q)

holds true for an arbitrary partition π and arbitrary positive integers p and q.

The main idea of the proof is to find a combinatorial interpretation of the recurrence (4.2) found by Lassalle [Las08a, Eq. (6.2)].

4.1. Lassalle’s recurrence. Following Lassalle [Las08a], we denote by π ∪ (s) the partition π with an extra part s added and by π \ (s) the partition π with one part s removed (we will not use this notation when π does not contain a part equal to s). We also write

π ∪ 1^{l} = π ∪ \underbrace{(1) ∪ ⋯ ∪ (1)}_{l times},
π_{↓(s)} = (π \ (s)) ∪ (s − 1),
π_{↑(rs)} = (π \ (r + s + 1)) ∪ (r) ∪ (s),
π_{↓(rs)} = ((π \ (r)) \ (s)) ∪ (r + s − 1).

Consider a rectangular Young diagram λ = p × q and a partition π such that m_{1}(π) = 0 (i.e., π does not contain any part equal to 1). Then Lassalle’s recurrence relation [Las08a, Eq. (6.2)], after adapting to our normalizations takes the form

(4.2) (\frac{p}{\sqrt{α}} − \sqrt{α}q) ∑_{r} r m_{r}(π) Ch_{π↓(r)}^{(α)}(λ)

+ ∑_{r} r m_{r}(π) ∑_{i=1}^{r−2} Ch_{π↑(i,r−i−1)}^{(α)}(λ)

− γ ∑_{r} r(r − 1) m_{r}(π) Ch_{π↓(r)}^{(α)}(λ)

+ ∑_{r,s} rs m_{r}(π)(m_{s}(π) − δ_{r,s}) Ch_{π↓(rs)}^{(α)}(λ)

= −|π| Ch_{π}^{(α)}(λ).

The difficulty in this formula comes from the fact that it was proved only under the assumption that m_{1}(π) = 0. In the following we will show how to overcome this issue.

4.2. Partitions with parts equal to 1. Luckily, Jack characters corresponding to a partition π with some parts equal to 1 can be deduced from the case without parts equal to 1. Indeed, strictly from the definition of Jack characters (2.1), we have

(4.3)  Ch_{π∪1^{l}}^{(α)}(λ) = (|λ| − |π|)_{l} Ch_{π}^{(α)}(λ).

The following result shows that an analogous property is satisfied by the orientability generating series Ĉh_{π}^{(α)}.

Lemma 4.2. Let π be a partition and λ be an arbitrary Young diagram. Then

(4.4)  Ĉh_{π∪1^{l}}^{(α)}(λ) = (|λ| − |π|)_{l} Ĉh_{π}^{(α)}(λ).

Proof. It is enough to prove that for any partition π we have

(4.5)  Ĉh_{π∪(1)}^{(α)}(λ) = (|λ| − |π|) Ĉh_{π}^{(α)}(λ).

For a partition π, let F_{π} be the set of pairs (M′, ≺), where M′ is a map with face-type π and history ≺. More explicitly: we start by fixing two pairings B′, W′ of the same set S′ so that (B′, W′) has type π. Then maps of face-type π are triples (B′, W′, E′), where E′ is a pairing of S′. In other words, each element of F_{π} can be viewed as a pair-partition E′ of S′, equipped with some linear order on the pairs.

Consider two elements b_{1}, b_{2} that are not in S′ and let S := S′ ⊔ {b_{1}, b_{2}}. We also consider the pairings B := B′ ⊔ {{b_{1}, b_{2}}} and W := W′ ⊔ {{b_{1}, b_{2}}} of S. The couple (B, W) has type π ∪ (1). Hence maps of face type π ∪ (1) are triples M = (B, W, E), where E is an arbitrary pairing of S.

If (M, ≺) ∈ F_{π∪(1)} is such that {b_{1}, b_{2}} is a pair of E, we say that (M, ≺ ) ∈ F_{π∪(1)}^{0}; in the other case we say that (M, ≺) ∈ F_{π∪(1)}^{1}. This yields a disjoint decomposition

(4.6)  F_{π∪(1)} = F_{π∪(1)}^{0} ⊔ F_{π∪(1)}^{1}.

Let H: F_{π∪(1)} → F_{π} be a function H: (M, ≺) ↦ (M′, ≺′) with M′ = (B, W, E) defined as follows:

• If (M, ≺) ∈ F_{π∪(1)}^{0}, then E′ := E \ {{b_{1}, b_{2}}} is defined as the pairing E with the pair {b_{1}, b_{2}} removed; as the linear order ≺′ we take the restriction of ≺ to E′ ⊂ E.

In this case, M, viewed as a bicolored graph, is a disjoint union of the bicolored graph M′ and the bicolored graph consisting of two vertices connected by the edge {b_{1}, b_{2}}. Thus the number of embeddings of M into the Young diagram λ is simply a product of N_{M′}^{(1)}(λ) and the number of embeddings of a single edge into the Young diagram λ (the latter number of embeddings is equal to |λ|, because any box of the Young diagram λ can be the image of the edge, see Section 1.6). The process of calculating mon_{M,≺} is almost identical to the analogous process of calculating mon_{M′,≺′}, except for the additional edge {b_{1}, b_{2}} which is clearly a straight edge. Thus

N_{M}^{(1)}(λ) = |λ| N_{M′}^{(1)}(λ),
|V_{∘}(M)| = |V_{∘}(M′)| + 1,
|V_{•}(M)| = |V_{•}(M′)| + 1,
mon_{M,≺} = mon_{M′,≺′} .

The first three equations also imply that

N_{M}^{(α)}(λ) = |λ| N_{M′}^{(α)}(λ).

• Let (M, ≺) ∈ F_{π∪(1)}^{1}. The edge-sides b_{1} and b_{2} appear in two different edges {e_{1}, b_{i}}, {e_{2}, b_{j}} ∈ E; we choose the indices {i, j} = {1, 2} in such a way that {e_{1}, b_{i}} ≺ {e_{2}, b_{j}}. Then we set

E′ := E_{{b_{1},b_{2}}} = (E ∪ {{e_{1}, e_{2}}}) \ {{e_{1}, b_{i}}, {e_{2}, b_{j}}}.

As the linear order ≺′ we take the unique linear order on E′ that coincides with ≺ on the intersection E ∩ E′ of their domains and such that for any pair P ∈ E ∩ E′ we have

P ≺′ {e_{1}, e_{2}} if and only if P ≺ {e_{2}, b_{j}};

in other words, the order ≺′ is obtained from ≺ by replacing the pair {e_{2}, b_{j}} by {e_{1}, e_{2}} and by removing the pair {e_{1}, b_{i}}.

The map M is obtained from M′ by replacing the edge {e_{1}, e_{2}} by a pair of edges in such a way that a new face is created (this face corresponds to the bigon B = {b_{1}, b_{2}} in L(B, W)). This means that, as a bicolored graph, M is obtained from the graph M′ by replacing one of the edges by a pair of edges, hence N_{M}^{(α)} = N_{M′}^{(α)}. The process of calculating mon_{M,≺} is almost identical to the analogous process of calculating mon_{M′,≺′}, except for the edge {e_{1}, b_{i}}, which is the edge out of the two edges adjacent to the bigon B which is removed first. This edge is clearly an interface edge. Thus,

N_{M}^{(1)}(λ) = N_{M′}^{(1)}(λ),
|V_{∘}(M)| = |V_{∘}(M′)|,
|V_{•}(M)| = |V_{•}(M′)|,
mon_{M,≺} = \frac{1}{2} mon_{M′,≺′} .

The first three equations imply that

N_{M}^{(α)}(λ) = N_{M′}^{(α)}(λ).

This concludes the definition of the map H.

The left-hand side of (4.5) is equal to

(4.7) Ĉh_{π∪(1)}^{(α)}(λ) = ∑_{(M,≺)∈F_{π∪(1)}} \frac{(−1)^{ℓ(π)+1}}{(|π| + 1)!} (−1)^{|V_{•}(M)|} mon_{M,≺} N_{M}^{(α)}(λ)

= ∑_{(M,≺)∈F_{π∪(1)}^{0}} \frac{(−1)^{ℓ(π)}}{(|π| + 1)!} (−1)^{|V_{•}(M′)|} mon_{M′,≺′} |λ| N_{M′}^{(α)}(λ)

− ∑_{(M,≺)∈F_{π∪(1)}^{1}} \frac{(−1)^{ℓ(π)}}{(|π| + 1)!} (−1)^{|V_{•}(M′)|} mon_{M′,≺′} \frac{1}{2} N_{M′}^{(α)}(λ),

where (M′, ≺′) is the image of (M, ≺) under H, and in the last equality we used the decomposition (4.6).

In the following we will show that for each (M′, ≺′) ∈ F_{π} its preimage fulfills

|H^{−1}(M′, ≺′) ∩ F_{π∪(1)}^{0}| = |π| + 1,
|H^{−1}(M′, ≺′) ∩ F_{π∪(1)}^{1}| = 2 (|π| + 1)| π|.

First observe that, for all pairs (M, ≺) ∈ H^{−1}(M′, ≺′)∩F_{π∪(1)}^{0}, the maps M are all the same: their edge pairing is given by E = E′ ∪ {{b_{1}, b_{2}}}. Moreover, the order ≺ is obtained from the order ≺′ by adding the additional pair {b_{1}, b_{2}} anywhere between pairs of E′, and this can be done in |π| + 1 ways.

Similarly, consider (M, ≺) ∈ H^{−1}(M′, ≺′) ∩ F_{π∪(1)}^{1}. Then E is obtained from E′ by removing some pair {e_{1}, e_{2}} and adding the pairs {e_{1}, b_{i}} and {e_{2}, b_{j}} for some choice of {i, j} = {1, 2}. Since the edges e_{1} and e_{2} play different roles (because by convention {e_{1}, b_{i}} ≺ {e_{2}, b_{j}}, we have altogether 4 choices for doing this for each edge {e_{1}, e_{2}}. The pair {e_{1}, e_{2}} ∈ E′ can be equivalently specified by saying that there are ℓ elements which are smaller than {e_{1}, e_{2}} (with respect to ≺′) with 0 ≤ ℓ ≤ |π| − 1. The linear order ≺ is obtained by replacing the pair {e_{1}, e_{2}} by {e_{2}, b_{j}} and by adding the pair {e_{1}, b_{i}} in such a way that {e_{1}, b_{i}} ≺ {e_{2}, b_{j}}; there are ℓ+1 choices for this. Thus the total number of choices is equal to

∑_{0≤ℓ≤|π|−1} 4(ℓ + 1) = 2 (|π| + 1) |π|,

just as we claimed.

Concluding, from (4.7) we see that

Ĉh_{π∪(1)}^{(α)}(λ)

= ∑_{(M′,≺′)∈F_{π}} \frac{(−1)^{ℓ(π)}}{(|π|)! (|π| + 1)} (−1)^{|V_{•}(M′)|}

× mon_{M′,≺′} N_{M′}^{(α)}(λ) (|λ| (|π| + 1) − 2 (|π| + 1) |π| \frac{1}{2})

= (|λ| − |π|) × ∑_{(M′,≺′)∈F_{π}} \frac{(−1)^{ℓ(π)}}{(|π|)!} (−1)^{|V_{•}(M′)|} mon_{M′,≺′} N_{M′}^{(α)}(λ)

= (|λ| − |π|) Ĉh_{π}^{(α)}(λ),

which finishes the proof. □

Corollary 4.3. If the answer for Question 1.3 is positive for some partition π and some Young diagram λ, it is also true for π′ := π ∪ 1 and λ.

Proof. This follows from the recurrence relations (4.3) and (4.4) □

4.3. Recurrence relation for the orientability generating series. In this section we shall see that the orientability generating series Ĉh_{π}^{(α)}(p × q) — when evaluated at a rectangular Young diagram — satisfies a recurrence relation analogous to (4.2).

There is an important simplification when we restrict our attention to a rectangular Young diagram, due to the following lemma.

Lemma 4.4. For a rectangular Young diagram λ = p × q, the number of embeddings of a bicolored graph G into λ is given by the particularly simple formula

N_{G}^{(1)}(λ) = p^{|V_{•}(G)|} q^{|V_{∘}(G)|}.

Proof. This is a particular case of [FŚ11b, Lemma 3.9]. □

We can now prove the following.

Proposition 4.5. If λ = p × q is a rectangular Young diagram and π is a partition such that m_{1}(π) = 0, then

(4.8) (\frac{p}{\sqrt{α}} − \sqrt{α}q) ∑_{r≥1} r m_{r}(π) Ĉh_{π↓(r)}^{(α)}(λ)

(removing a leaf)

+ \underbrace{∑_{r≥1} r m_{r}(π) ∑_{i=1}^{r−2} Ĉh_{π↑(i,r−i−1)}^{(α)}(λ)}_{(removing a straight edge)}

− \underbrace{γ ∑_{r≥1} r(r − 1) m_{r}(π) Ĉh_{π↓(r)}^{(α)}(λ)}_{(removing a twisted edge)}

+ \underbrace{∑_{r,s≥1} rs m_{r}(π)(m_{s}(π) − δ_{r,s}) Ĉh_{π↓(rs)}^{(α)}(λ)}_{(removing an interface edge)}

= −|π| Ĉh_{π}^{(α)}(λ).

The comments below the curly braces concerning the individual summands on the left-hand side of this recurrence relation are connected to its proof; see below.

Remark 4.6. Notice that the assumption m_{1}(π) = 0 in the proposition above means that all the sums on the left hand side of (4.8) can, alternatively, run over r ≥ 2 instead of r ≥ 1.

Proof. Clearly, (3.2) is equivalent to the recursive relationship

mon_{M,≺} = mon_{M,E} · mon_{M\E,≺′},

where E is the first edge according to the linear order ≺, and ≺′ is the restriction of ≺ to the edges of E(M \ E).

Using (1.9), (1.2), (3.3), and Lemma 4.4, the right-hand side of (4.8) can be written as

(4.9) − |π| Ĉh_{π}^{(α)}(λ)

= \frac{(−1)^{ℓ(π)−1}}{(|π| − 1)!} ∑_{(M,≺)} (−\frac{p}{\sqrt{α}})^{|V_{•}(M)|} (q \sqrt{α})^{|V_{∘}(M)|} mon_{M,≺},

where the sum runs over maps of face type π with a specific history. In the following we will use the notation

contribution_{M,≺}(λ) := (−\frac{p}{\sqrt{α}})^{|V_{•}(M)|} (q \sqrt{α})^{|V_{∘}(M)|} mon_{M,≺}

for the contribution of the pair (M, ≺) to the sum on the right-hand side of (4.9).

Recall that the summation in (4.9) should be interpreted as follows: we fix a couple (B, W) of pairings of type π, and we sum over all choices of the pairing E of the same ground set S; we also sum over all choices of the linear order ≺ on E. For such a map M = (B, W, E) and a linear order ≺, we denote by E = {s_{1}, s_{2}} the first edge according to the linear order ≺ and by ≺′ the restriction of the linear order ≺ to the edges of E \ {E}.

The summation over (M, ≺) can be seen alternatively as follows: we first choose the first edge E and then sum over all choices of the couple (E′, ≺′), where E′ = E \ {E} is a pairing of S \ E and ≺′ a linear order on E′. This summation over E′ can be interpreted as a summation over all choices of the map M′ = (B_{E}, W_{E}, E′) of face-type corresponding to the type of the couple (B_{E}, W_{E}). Note that the map M′ corresponds to M \ E. We shall use this idea repeatedly in the proof.

We split our sum depending on the type (straight, twisted, or interface) of the edge E in the map M. Note that, as B and W are fixed, this type depends only on the pair E, not on the remaining pairs in E. According to the classification from Section 3.5, there are the following possibilities:

The edge E is straight and both endpoints of E have degree 1. This is not possible since it would imply that one of the faces of M is a bigon; thus m_{1}(π) ≥ 1.

The edge E is straight (hence mon_{M,E} = 1) and only the black (respectively white) endpoint of E has degree 1 (i.e., it is a leaf). In other terms, the pair E belongs also to the pairing B (respectively W). We consider the map M \ E; recall that it has one black (respectively white) vertex less than M (the leaf extremity has been removed together with the edge). It follows that

(4.10)  contribution_{M,≺}(λ) = \frac{−p}{\sqrt{α}} contribution_{M\E,≺′}(λ);

respectively

contribution_{M,≺}(λ) = q \sqrt{α} contribution_{M\E,≺′}(λ).

Fix the black vertex B = {b_{1}, b_{2}} ∈ B, and let us consider the total contribution of the couples (E, ≺) such that B is the black endpoint of E; in other words E = B. This means that E = E′ ⊔{B}, where E′ is a pairing of S \ B, and thus B_{B} = B \ {B}. Therefore (B_{E}, W_{E}) = (B_{B}, W_{B}) is a couple of pairings of S \ B of type π_{↓(r)}, where 2r is the number of edge-sides in the polygon of L(B, W) containing B. It follows that the summation over all choices of the pairing E′ corresponds to a summation over all choices of the map M′ of face-type π_{↓(r)}. By definition, the map M′ = (B_{B}, W_{B}, E′) is equal to M \ E, and its contribution appears as the last factor on the right-hand side of Equation (4.10) above.

Therefore, for a fixed pair B ∈ B that belongs to a polygon of size 2r of L(B, W), the total contribution to the right-hand side of (4.9) of the couples (E, ≺) as above is given by

\frac{(−1)^{ℓ(π)−1}}{(|π| − 1)!} ∑_{(M′,≺′)} \frac{−p}{\sqrt{α}} contribution_{M′,≺′}(λ) = \frac{p}{\sqrt{α}} Ĉh_{π_{↓(r)}}(λ).

For r ≥ 2, there are m_{r}(π) polygons of size 2r in L(B, W), and each of them contains r pairs of B. Hence the total contribution of the pairs (M, ≺) such that the first edge E belongs to B (i.e., its black extremity is a leaf) is equal to

\frac{p}{\sqrt{α}} ∑_{r≥2} rm_{r}(π) Ĉh_{π_{↓(r)}}(λ).

Similarly, the total contribution of pairs (M, ≺) such that the first edge E belongs to W is equal to

−q \sqrt{α} ∑_{r≥2} rm_{r}(π) Ĉh_{π_{↓(r)}}(λ).

Finally, both cases together yield the first term of the recurrence relation (4.8).

The edge E is straight (hence mon_{M,E} = 1) and no endpoint of E has degree 1. In this case, we have

contribution_{M,≺}(λ) = contribution_{M\E,≺′}(λ).

By definition, E = {s_{1}, s_{2}} being straight means that both of its edge-sides s_{1} and s_{2} belong to the same polygon F ∈ L(B, W). Moreover, there is an even number of edge-sides, say 2i (with i > 0), between s_{1} and s_{2} if we turn around F in one direction, and also an even number of edge-sides, say 2j (with j > 0), if we turn around the face in the other direction.

Fix such a pair E of edge-sides. Then (B_{E}, W_{E}) is a couple of pairings of S \ E of type π_{↑(i,j)} (see Section 3.7.1). As before, the summation over all choices of (E, ≺) such that E is the first edge is equivalent to a summation over all choices of the pairing E′ of S \ E and all choices of the order ≺′ on E′. By definition, this corresponds to a summation over all choices of (M′, ≺′), where M′ = (B_{E}, W_{E}, E′) = M \ E runs over maps of face-type π_{↑(i,j)}. Therefore, for a fixed E, the total contribution of the corresponding pairs (M, ≺) is equal to

∑_{(M′,≺′)} \frac{(−1)^{ℓ(π)−1}}{(|π| − 1)!} contribution_{M′,≺′}(λ) = Ĉh_{π_{↑(i,j)}}^{(α)}(λ).

Let us count how many pairs E correspond to a given value of i and j. First, s_{1} must be chosen in some face F containing 2r edge-sides. There are m_{r}(π) such faces and 2r edge-sides in each of them, so there are 2rm_{r}(π) possible choices for s_{1}. Once s_{1} is fixed, there are two possible choices for s_{2} (and only one choice if i = j): we fix arbitrarily a direction to turn around the face F, and then s_{2} must be the (i + 1)-st or (j + 1)-st edge-side after s_{1} in this direction. As s_{1} and s_{2} play identical roles and E is a nonordered pair, the number of pairs E corresponding to a pair of values {i, j} is equal to (2 − δ_{i,j})rm_{r}(π). Hence the total contribution of the couples (M, ≺) such that E is straight and none of its endpoints is a leaf is equal to

∑_{\begin{matrix}r≥1 \\ \{i,j\}: \\ i,j≥1, \\ i+j=r−1 \end{matrix}}(2 − δ_{i,j})rm_{r}(π)Ĉh_{π_{↑(i,j)}}^{(α)}(λ) = ∑_{\begin{matrix}r≥1 \\ i,j≥1 \\ i+j=r−1 \end{matrix}} rm_{r}(π)Ĉh_{π_{↑(i,j)}}^{(α)}(λ).

Clearly, this is equal to the second summand on the left-hand side of (4.8).

The edge E is twisted and thus mon_{M,E} = γ. In this case, no endpoint of E has degree 1, hence

contribution_{M,≺}(λ) = γ · contribution_{M\E,≺′}(λ).

We fix a pair E = {s_{1}, s_{2}} such that both edge-sides s_{1} and s_{2} lie in a polygon F of L(B, W) and are in an odd position. As above, if we fix the number 2r of the edge-sides in F, there are 2rm_{r}(π) possible choices for s_{1}. Once s_{1} is fixed, there are r − 1 possible choices for s_{2}, which makes r(r − 1)m_{r}(π) choices for the pair {s_{1}, s_{2}} (recall the symmetry between s_{1} and s_{2}).

Fix such an edge E. The couple (B_{E}, W_{E}) of pairings of S \ E has type π ↓ (r) (see Section 3.7.4). Hence the summation over all choices of (M, ≺) such that E is the first edge is equivalent to a summation over maps M \ E of face-type π ↓ (r).

Finally, the total contribution of the couples (M, ≺) with first edge twisted is equal to

∑_{r} r(r − 1) m_{r}(π) ∑_{(M′,≺′)} \frac{(−1)^{ℓ(π)−1}}{(|π| − 1)!} γ · contribution_{M′,≺′}(λ)

= −γ ∑_{r} r(r − 1) m_{r}(π) Ĉh_{π↓(r)}(λ),

where the summation on the left-hand side is over maps M′ with face-type π ↓ (r). Clearly, this is equal to the third summand on the left-hand side of (4.8).

The edge E is interface and thus mon_{M,E} = \frac{1}{2}. In this case, no endpoint of E has degree 1, hence

contribution_{M,≺}(λ) = \frac{1}{2} contribution_{M\E,≺′}(λ).

Fix a pair E = {s_{1}, s_{2}} of edge-sides lying in two different polygons F_{1} and F_{2} of L(B, W). Suppose F_{1} contains 2r edge-sides, while F_{2} contains 2s. Then (B_{E}, W_{E}) has face-type π ↓ (rs) (see Section 3.7.6). The summation over all choices of (M, ≺) such that E is the first edge is equivalent to a summation over all choices of the map M′ = M \ E of face-type π ↓ (rs). Therefore, for a fixed pair E as above, the total contribution of the couples (M, ≺) with first edge equal to E is given by

∑_{(M′,≺′)} \frac{(−1)^{ℓ(π)−1}}{(|π| − 1)!} · \frac{1}{2} contribution_{M′,≺′}(λ) = \frac{1}{2}Ĉh_{π↓(rs)}(λ).

How many pairs E correspond to a given pair {r, s}? First, one should choose s_{1} in a polygon of size 2r or 2s, let us say 2r, of L(S_{1}, S_{2}). There are 2rm_{r}(π) choices for that. Then we choose s_{2} in a polygon of size 2s of L(S_{1}, S_{2}) (recall that, if r = s, this polygon has to be different from the first one): there are 2s(m_{s}(π) − δ_{r,s}) choices for that. If r = s, then s_{1} and s_{2} play analogous roles (if r ≠ s, we broke the symmetry by assuming that s_{1} lies in a polygon of size 2r), so one should divide by 2 in order to count unordered pairs {s_{1}, s_{2}} instead of ordered pairs. Finally, we obtain that the total contribution of the couples (M, ≺) with first edge being interface is equal to

∑_{\{r,s\}} \frac{4}{1 + δ_{r,s}} rs m_{r}(π)(m_{s}(π) − δ_{r,s}) \frac{1}{2}Ĉh_{π↓(rs)}(λ)

= ∑_{r,s} rs m_{r}(π)(m_{s}(π) − δ_{r,s}) Ĉh_{π↓(rs)}(λ).

Clearly, this is equal to the fourth summand on the left-hand side of (4.8).

By putting together all the contributions of the cases considered above, we obtain the recurrence (4.8). This finishes the proof of the proposition.

□

4.4. Proof of Theorem 4.1. We use induction on |π|. For |π| = 0, there is

only the empty partition π = ∅; clearly in this case Ch_{∅}^{(α)}(λ) = Ĉh_{∅}^{(α)}(λ) = 1. Since this is a somewhat pathological case (empty polygon, empty function, etc.), in order to avoid difficulties with the start of the induction, we also consider separately the case |π| = 1, for which there is only one parti-

tion, namely π = (1). In this case, we easily get Ch_{1}^{(α)}(λ) = Ĉh_{1}^{(α)}(λ) = |λ|, so that that start of the induction is established.

Let us assume that the inductive hypothesis holds for all π such that |π| < n, and let π be a partition with |π| = n. In the case where m_{1}(π) ≥ 1, we apply (4.3) and (4.4), and the inductive hypothesis implies that (4.1) holds true for π as well.

In the case where m_{1}(π) = 0, we compare the left-hand side of (4.8) with the left-hand side of (4.2). From the inductive hypothesis it follows that they are equal; hence their right-hand sides must be equal as well. This concludes the proof of the inductive step. □

4.5. Proof of Theorem 1.5. The first part of Theorem 1.5 is restated in Theorem 4.1, hence it is enough to prove only the second part.

In the following we shall implicitly view α as a function of γ, where α(γ) was defined in the beginning of the proof of Lemma 2.4.

Let us fix integers i and ℓ with 1 ≤ i ≤ ℓ. We define

P̃ Q_{i} := {(P̃_{i} = (p_{1}, …, p_{ℓ}), Q = (q_{1}, …, q_{ℓ}), γ) :

p_{j} = 0 for all j ≠ i and

\sqrt{α}P̃_{i} × \frac{1}{\sqrt{α}}Q is a Young diagram\}.

Note that all Young diagrams appearing in this set are rectangular. Thus the first part of Theorem 1.5 implies that for any triple (P̃_{i}, Q, γ) ∈ P̃ Q_{i} the equality

(4.11)  Ch_{π}^{(α)} (\sqrt{α}P̃_{i} × \frac{1}{\sqrt{α}}Q) = Ĉh_{π}^{(α)} (\sqrt{α}P̃_{i} × \frac{1}{\sqrt{α}}Q)

holds true for any partition π.

Just as in Definition 1.4, we now view P = (p_{1}, …, p_{ℓ}) and Q = (q_{1}, …, q_{ℓ}) as sequences of indeterminates. Then, by Lemma 2.4, we know that each of the quantities

Ch_{π}^{(α)} (\sqrt{α}P × \frac{1}{\sqrt{α}}Q) and Ĉh_{π}^{(α)} (\sqrt{α}P × \frac{1}{\sqrt{α}}Q)

is a polynomial in the indeterminates γ, p_{1}, …, p_{ℓ}, q_{1}, …, q_{ℓ}. By substituting

P̃_{i} := (\underbrace{0, …, 0}_{i − 1 times}, p_{i}, \underbrace{0, …, 0}_{ℓ − i times}),

we see that each of the quantities

(4.12)  Ch_{π}^{(α)} (\sqrt{α}P̃_{i} × \frac{1}{\sqrt{α}}Q)

and

(4.13)  Ĉh_{π}^{(α)} (\sqrt{α}P̃_{i} × \frac{1}{\sqrt{α}}Q)

can be expressed as a polynomial in the indeterminates γ, p_{i}, q_{1}, …, q_{ℓ} (a priori the uniqueness of this polynomial might not be obvious; we shall discuss this issue in the following).

Moreover, for any triple (g, e, f) of non-negative integers, the following equality between the coefficients of the respective polynomials holds true:

[γ^{g}p_{i}^{e}q_{i}^{f}] Ch_{π}^{(α)} (\sqrt{α}P × \frac{1}{\sqrt{α}}Q) = [γ^{g}p_{i}^{e}q_{i}^{f}] Ch_{π}^{(α)} (\sqrt{α}P̃_{i} × \frac{1}{\sqrt{α}}Q) ,

and similarly

[γ^{g}p_{i}^{e}q_{i}^{f}] Ĉh_{π}^{(α)} (\sqrt{α}P × \frac{1}{\sqrt{α}}Q) = [γ^{g}p_{i}^{e}q_{i}^{f}] Ĉh_{π}^{(α)} (\sqrt{α}P̃_{i} × \frac{1}{\sqrt{α}}Q) .

Since equality (4.11) holds for any triple (P̃_{i}, Q, γ) ∈ P̃ Q_{i}, it follows — using the same technique as in the uniqueness part of the proof of Lemma 2.4 — that the quantities

Ch_{π}^{(α)} (\sqrt{α}P̃_{i} × \frac{1}{\sqrt{α}}Q) and Ĉh_{π}^{(α)} (\sqrt{α}P̃_{i} × \frac{1}{\sqrt{α}}Q)

are equal as polynomials in the indeterminates γ, p_{i}, q_{1}, …, q_{ℓ} (note that the same argument explains the uniqueness of the polynomials (4.12) and (4.13)). In particular, for any triple (g, e, f) of non-negative integers, the following equality between the coefficients of the respective polynomials in the indeterminates γ, p_{1}, …, p_{ℓ}, q_{1}, …, q_{ℓ} holds true:

[γ^{g}p_{i}^{e}q_{i}^{f}] Ch_{π}^{(α)} (\sqrt{α}P × \frac{1}{\sqrt{α}}Q) = [γ^{g}p_{i}^{e}q_{i}^{f}] Ĉh_{π}^{(α)} (\sqrt{α}P × \frac{1}{\sqrt{α}}Q) .

This finishes the proof. □

5. Support for the conjectures: special values of α

5.1. Reformulation of the results from [FŚ11b]. The purpose of this section is to explain how Equations (1.4) and (1.5) can be obtained easily from the results of [FŚ11b], even if the presentation there is a little bit different. We use boldface characters for the notation of [FŚ11b].

First, note the difference in the notation and in the normalization:

Ch_{π}^{(2)}(λ) = (\frac{1}{\sqrt{2}})^{|π|−ℓ(π)} Σ_{π}^{(2)}.

Note also that the roles of black and white vertices in the definition of N_{G} are inverted. Hence [FŚ11b, Theorem 5.2] with the notation of the present paper takes the form

Ch_{π}^{(2)}(λ) = (\frac{1}{\sqrt{2}})^{|π|−ℓ(π)} \frac{(−1)^{|π|}}{2^{ℓ(π)}} ∑_{M}(−2)^{|V_{∘}(M)|} N_{M}^{(1)},

where the sum runs over the maps of face-type π. This is clearly the same as Equation (1.4).

Equation (1.5) is deduced directly from (1.4) using the duality relation (2.5) and the fact that

N_{G}^{(α)}(λ′) = N_{G′}^{(1/α)}(λ),

where G′ is obtained from G by inverting the colors of the vertices.

5.2. The special cases α = \frac{1}{2} and α = 2.

Theorem 5.1. The answer for Question 1.3is positive for α = \frac{1}{2} and α = 2.

Proof. The condition α ∈ \{\frac{1}{2}, 2\} is equivalent to γ^{2} = \frac{1}{2}. This implies, by the same case analysis as in the proof of Lemma 3.7, that for any edge E of an arbitrary map M

mon_{M,E} = γ^{[|F(M)|−|V(M)|]−[|F(M\E)|−|V(M\E)|]+1}.

For an arbitrary history ≺, the exponents of γ in the product (3.2) form a telescoping sum, thus

mon_{M,≺} = γ^{|F(M)|−|V(M)|+|E(M)|} = γ^{ℓ(π)−|V(M)|+|π|},

where π is the face-type of M; in particular this expression does not depend on the choice of the history, hence

mon_{M} = γ^{ℓ(π)−|V(M)|+|π|}.

One can thus easily check that Ĉh_{π}^{(2)} coincides with (1.4), while Ĉh_{π}^{(1/2)} coincides with (1.5). □

6. Link with a positivity conjecture of Lassalle

In this section we often use the following parameter introduced by Lassalle:

β := α − 1.

6.1. Statement of Lassalle’s conjecture. Lassalle stated the following conjecture.

Conjecture 6.1 ([Las08a, Conjecture 1]). Let π be a partition such that m_{1}(π) = 0. Then (−1)^{|π|}ϑ_{π∪1^{n−|π|}}^{P ×Q}(α) is a polynomial in (P, −Q, β) with non-negative integer coefficients.

In the following we will prove (in Corollary 6.3) that our Main Conjecture 1.1 implies a weaker version of Conjecture 6.1, namely that the coefficients are non-negative rational numbers.

6.2. Positivity in multirectangular coordinates. Our first step is the following statement.

Theorem 6.2. Under the assumption that Main Conjecture 1.1 holds true, the quantity (−1)^{|π|} Ch_{π}^{(α)}(P × Q) is a polynomial in the variables (P/\sqrt{α}, −\sqrt{α}Q, −γ) with non-negative rational coefficients.

Proof. For a Young diagram P × Q given in multirectangular coordinates, the number of embeddings N_{M}^{(1)}(P × Q) takes a particularly simple form (see [FŚ11b, Lemma 3.9], where the notations are slightly different), for this reason, Equation (1.6) would imply that

Ch_{π}^{(α)}(P × Q) = (−1)^{ℓ(π)} ∑_{M} wt_{M}(γ)

× [ ∑_{φ: V_{•}(M)→ℕ^{⋆}} ∏_{l∈V_{•}(M)} (\frac{−p_{φ(l)}}{\sqrt{α}} ) · ∏_{l′∈V_{∘}(M)} (\sqrt{α} q_{ψ(l′)})] ,

where the first sum is over all bicolored maps M of face-type π, and ψ(l′) is defined as the maximum of φ(l) over all white neighbors l of the black vertex l′.

The quantity wt_{M}(γ) is a polynomial in γ with non-negative rational coefficients of the same parity as the Euler characteristic χ(M), that is, the same parity as |π| + ℓ(π) + |V(M)|. Rewriting the equation above as

(−1)^{|π|} Ch_{π}^{(α)}(P × Q) = ∑_{M} wt_{M}(−γ)

× [ ∑_{φ: V_{•}(M)→ℕ^{⋆}} ∏_{l∈V_{•}(M)} (\frac{p_{φ(l)}}{\sqrt{α}} ) · ∏_{l′∈V_{∘}(M)} (−\sqrt{α} q_{ψ(l′)})] ,

makes the assertion of the theorem obvious. □

Corollary 6.3. We assume that Main Conjecture 1.1holds true. Let π be an arbitrary partition. Then (−1)^{|π|}ϑ_{π∪1^{n−|π|}}^{P ×Q}(α) is a polynomial in (P, −Q, β) with non-negative rational coefficients.

Proof. Using (2.4), we obtain

(−1)^{|π|}ϑ_{π∪1^{n−|π|}}^{P ×Q}(α) = ∑_{M} \sqrt{α}^{2|V_{∘}(M)|+|π|−ℓ(π)−|V(M)|} wt_{M}(−γ)

× [ ∑_{φ: V_{•}(M)→ℕ^{⋆}} ∏_{l∈V_{•}(M)} p_{φ(l)} · ∏_{l′∈V_{∘}(M)} (−q_{ψ(l′)})] .

Recall that wt_{M}(γ) is a polynomial in γ of degree at most

χ(M) = 2·(number of connected components of M)−ℓ(π)+|π|−|V(M)|

and with the same parity as χ(M). The number of connected components of M is at most the number of white vertices, and since −γ = \frac{β}{\sqrt{α}} and α = β + 1 we see that

\sqrt{α}^{2|V_{∘}(M)|+|π|−ℓ(π)−|V(M)|} wt_{M}(−γ)

is a polynomial in β with non-negative rational coefficients. This concludes the proof. □

Remark 6.4. If Main Conjecture 1.1 is true with a weight wt_{M} with integer coefficients (as polynomial in γ), then it also implies the integrality statements in [Las08a, Conjecture 1] and [Las09, Conjecture 1.2].

7. Computer exploration and the counterexample

7.1. Counterexample π = (9). For π = (9) a computer calculation shows that

(7.1) Ĉh_{(9)}^{(α)}(P × Q) − Ch_{(9)}^{(α)}(P × Q)

= \frac{41}{70}(2γ^{2} − 1) ∑_{i<j<k} p_{i}p_{j}p_{k}(q_{k} − q_{j})(q_{i} − q_{j})q_{k},

which might be non-zero for multirectangular Young diagrams consisting of at least ℓ ≥ 3 rectangles. It is worth pointing out that this is not a counterexample for Conjecture 1.6. However, it shows that the answer to Question 1.3 might be negative for some specific choices of α and λ.

For (7.1), the quantity Ĉh_{π}^{(α)}(P ×Q) was computed using the very definition given in this article. Computing Ch_{π}^{(α)}(P × Q) is a bit harder (while shorter in practice): we used some data made available by Lassalle [Las08b], that express it in terms of the free cumulants. (Lassalle gave an algorithm to do this computation in [Las09, Section 9]. But as his data were made available, we did not implement it again.) Then the free cumulant R_{k}(P × Q) can be computed using the recursive structure of bicolored planted plane trees (see [Rat08, Eqs. (10), (11) and (12)]).

The calculation of (7.1) took a week of computer time. Finding this counterexample was only possible because the theoretical results in this paper and some additional tricks allow to reduce the computational complexity. (The naive algorithm which lists all maps with all histories would have to consider 17!! · 9! ≈ 1.25 × 10^{13} cases.) An analogous calculation for π = (10) would be, for the moment, rather challenging.

7.2. Another weight. We have also been testing numerically another candidate for the weight in Main Conjecture 1.1. The idea was to define mon′_{M} as mon_{M,<} for some specific history <. We chose this history as follows:

• first erase the edge containing the edge-side with the smallest label (denote it by s_{0});

• then remove the edges containing

E ∘ W(s_{0}), (E ∘ W)^{2}(s_{0}), …,

until you reach s_{0} again (here the pairings E and W are viewed as fixed point-free involutions);

• then start again with the edge-side with the smallest label among the remaining edges.

This definition was inspired by the work of La Croix on the b-Conjecture [LC09, Sec. 4.1]. This new candidate weight mon′_{M} is much easier to evaluate as we do not need to consider all possible histories.

This new weight mon′_{M} gives the correct answer in the cases where α ∈ {1/2, 2}, just as mon_{M} does (Theorem 5.1). Indeed, we have proved that in this case mon_{M,≺} does not depend on the choice of the history ≺, thus any specific choice of history (or any mean over some set of histories) works fine.

We have observed numerically that this weight is a solution to Main Conjecture 1.1 for any π of size at most 8 as well as for π = (9), but not for π = (10) and π = (5, 4).

Also, this weight seems to work for rectangular shapes, but we are unable to prove it. Numerical data suggest that it also works for a superposition of (at most) two rectangles λ = (p_{1}, p_{2}) × (q_{1}, q_{2}).

Acknowledgments

We thank Michael La Croix for a very interesting discussion concerning the b-Conjecture.

We also thank Michel Lassalle for making his data available on his webpage [Las08b]. Computer exploration for this paper was partly driven by the open-source mathematical software Sage [S^{+}14] and its algebraic combinatorics features developed by the Sage-Combinat community [SCc14].

M.D.’s research has been supported by a grant of the Narodowe Centrum Nauki (2011/03/N/ST1/00117). In the initial phase of research, P.Ś. was a holder of a fellowship of the Alexander von Humboldt–Stiftung. P.Ś.’s research has been supported by a grant of the Deutsche Forschungsgemeinschaft (SN 101/1-1). V.F.’s research is partially supported by the ANR grant psyco (ANR-11-JS02-001).

References

[BH08] B. A. Bernevig and F. D. M. Haldane. Model fractional quantum Hall states and Jack polynomials. Phys. Rev. Lett., 100:246802, 2008.

[Bia98] P. Biane. Representations of symmetric groups and free probability. Adv. Math., 138(1):126–181, 1998.

[BJ07] D. R. L. Brown and D. M. Jackson. A rooted map invariant, non-orientability and Jack symmetric functions. J. Combin. Theory Ser. B, 97(3):430–452, 2007.

[DF14] M. Dołęga and V. Féray. Gaussian fluctuations of Young diagrams and structure constants of Jack characters. Preprint , 2014.

[DFŚ10] 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.

[Fér09] V. Féray. Combinatorial interpretation and positivity of Kerov’s character polynomials. J. Algebraic Combin., 29(4):473–507, 2009.

[Fér10] V. Féray. Stanley’s formula for characters of the symmetric group. Ann. Comb.,

13(4):453–461, 2010.

[FJMM02] B. Feigin, M. Jimbo, T. Miwa, and E. Mukhin. A differential ideal of symmetric polynomials spanned by Jack polynomials at β = −(r − 1)/(k + 1). Int. Math. Res. Not., 2002(23):1223–1237, 2002.

[FŚ11a] V. Féray and P. Śniady. Asymptotics of characters of symmetric groups related

to Stanley character formula. Ann. of Math. (2), 173(2):887–906, 2011.

[FŚ11b] V. Féray and P. Śniady. Zonal polynomials via Stanley’s coordinates and free

cumulants. J. Algebra, 334:338–373, 2011.

[GJ96a] I. P. Goulden and D. M. Jackson. Connection coefficients, matchings, maps and combinatorial conjectures for Jack symmetric functions. Trans. Amer. Math. Soc., 348(3):873–892, 1996.

[GJ96b] I. P. Goulden and D. M. Jackson. Maps in locally orientable surfaces, the double coset algebra, and zonal polynomials. Canad. J. Math., 48(3):569–584, 1996.

[GR05] A. Garsia and J. B. Remmel. Breakthroughs in the theory of Macdonald polynomials. Proc. Natl. Acad. Sci. USA, 102(11):3891–3894 (electronic), 2005.

[IO02] V. Ivanov and G. Olshanski. Kerov’s central limit theorem for the Plancherel measure on Young diagrams. In Symmetric functions 2001: surveys of developments and perspectives, volume 74 of NATO Sci. Ser. II Math. Phys. Chem., pp. 93–151. Kluwer Acad. Publ., Dordrecht, 2002.

[Jac71] H. Jack. A class of symmetric polynomials with a parameter. Proc. Roy. Soc. Edinburgh Sect. A, 69:1–18, 1970/1971.

[Kad97] K. W. J. Kadell. The Selberg-Jack symmetric functions. Adv. Math., 130(1):33–102, 1997.

[Ker93] S. Kerov. Transition probabilities of continual Young diagrams and the Markov moment problem. Funct. Anal. Appl., 27(3):104–117, 1993.

[KO94] 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.

[Las08a] M. Lassalle. A positivity conjecture for Jack polynomials. Math. Res. Lett., 15(4):661–681, 2008.

[Las08b] M. Lassalle. Website Jack polynomials and free cumulants.

http://igm.univ-mlv.fr/~lassalle/free.html  , Accessed:

1/12/2012.

[Las09] M. Lassalle. Jack polynomials and free cumulants. Adv. Math., 222(6):2227– 2269, 2009.

[LC09] M. A. La Croix. The combinatorics of the Jack parameter and the genus series for topological maps. Ph.D. thesis, University of Waterloo, 2009.

[LV95] L. Lapointe and L. Vinet. A Rodrigues formula for the Jack polynomials and the Macdonald–Stanley conjecture. Internat. Math. Res. Notices, 1995(9):419–424, 1995.

[LV97] L. Lapointe and L. Vinet. Rodrigues formulas for the Macdonald polynomials. Adv. Math., 130(2):261–279, 1997.

[Mac95] I. G. Macdonald. Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, second edition, 1995. With contributions by A. Zelevinsky, Oxford Science Publications.

[NS06] A. Nica and R. Speicher. Lectures on the combinatorics of free probability, volume 335 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 2006.

[Rat08] A. Rattan. Stanley’s character polynomials and coloured factorizations in the symmetric group. J. Combin. Theory Ser. A, 114(4):535–546, 2008.

[S^{+}14] W. A. Stein et al. Sage Mathematics Software (Version 6.2). The Sage Devel-

         opment Team, 2014. http://www.sagemath.org .

[SCc14] The Sage-Combinat community. Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2014.

         http://combinat.sagemath.org  .

[Śni14] P. Śniady. Top degree of Jack characters and enumeration of maps. In prepara-

tion, 2014.

[Sta04] R. P. Stanley. Irreducible symmetric group characters of rectangular shape. Sém. Lothar. Combin., 50:Art. B50d, 11 pp. (electronic), 2003/04.

[Sta89] R. P. Stanley. Some combinatorial properties of Jack symmetric functions. Adv. Math., 77(1):76–115, 1989.

[Sta06] R. P. Stanley. A conjectured combinatorial interpretation of the normalized irreducible character values of the symmetric group. Manuscript , 2006.

LIAFA, Université Paris 7, Case 7014, 75205 Paris Cedex 13, France Instytut Matematyczny, Uniwersytet Wrocłąwski, pl. Grunwaldzki 2/4,

50-384 Wrocłąw, Poland

  E-mail address: dolega@liafa.univ-paris-diderot.fr

LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33 400 Talence, France.

Current address: Institut für Mathematik, Universität Zürich, Winterthurerstraße 190, CH-8057 Switzerland

  E-mail address: valentin.feray@math.uzh.ch

Wydział Matematyki i Informatyki, Uniwersytet im. Adama Mickiewicza, Collegium Mathematicum, Umultowska 87, 61-614 Poznań, Poland,

Instytut Matematyczny, Polska Akademia Nauk, ul. Śniadeckich 8, 00-956 Warszawa, Poland.

  E-mail address: piotr.sniady@amu.edu.pl