# Application of graph combinatorics to rational identities of type A (extended abstract)

Adrien Boussicault, Valentin Féray

► To cite this version:

Adrien Boussicault, Valentin Féray. Application of graph combinatorics to rational identities of type A (extended abstract). 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), Jul 2009, Hagenberg, Austria. pp.231-242. hal-00418472

HAL Id: hal-00418472

https://hal.science/hal-00418472v1

Submitted on 18 Sep 2009

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Application of graph combinatorics to rational identities of type $A^\dagger$

Adrien Boussicault¹ and Valentin Féray¹

¹ Université Paris-Est, Institut d'électronique et d'informatique Gaspard-Monge, 77454 Marne-la-Vallée Cedex 2

To a word $w$, we associate the rational function $\Psi_w = \prod (x_{w_i} - x_{w_{i+1}})^{-1}$. The main object, introduced by C. Greene to generalize identities linked to Murnaghan-Nakayama rule, is a sum of its images by certain permutations of the variables. The sets of permutations that we consider are the linear extensions of oriented graphs. We explain how to compute this rational function, using the combinatorics of the graph $G$. We also establish a link between an algebraic property of the rational function (the factorization of the numerator) and a combinatorial property of the graph (the existence of a disconnecting chain).

**Résumé** : À un mot $w$, nous associons la fonction rationnelle $\Psi_w = \prod (x_{w_i} - x_{w_{i+1}})^{-1}$. L'objet principal, introduit par C. Greene pour généraliser des identités rationnelles liées à la règle de Murnaghan-Nakayama, est une somme de ses images par certaines permutations des variables. Les ensembles de permutations considérés sont les extensions linéaires des graphes orientés. Nous expliquons comment calculer cette fonction rationnelle à partir de la combinatoire du graphe $G$. Nous établissons ensuite un lien entre une propriété algébrique de la fonction rationnelle (la factorisation du numérateur) et une propriété combinatoire du graphe (l'existence d'une chaîne le déconnectant).

**Keywords:** Rational functions, posets, maps

## 1 Introduction

A partially ordered set (poset) $\mathcal{P}$ is a finite set $V$ endowed with a partial order. By definition, a word $w$ containing exactly once each element of $V$ is called a *linear extension* if the order of the letters is compatible with $\mathcal{P}$ (if $a \leq_{\mathcal{P}} b$, then $a$ must be before $b$ in $w$). To a linear extension $w = v_1v_2\dots v_n$, we associate a rational function:

$$ \psi_w = \frac{1}{(x_{v_1} - x_{v_2}) \cdot (x_{v_2} - x_{v_3}) \dots (x_{v_{n-1}} - x_{v_n})} $$

We can now introduce the main object of the paper. If we denote by $\mathcal{L}(\mathcal{P})$ the set of linear extensions of $\mathcal{P}$, then we define $\Psi_{\mathcal{P}}$ by:

$$ \Psi_{\mathcal{P}} = \sum_{w \in \mathcal{L}(\mathcal{P})} \psi_w. $$

<footnote>†this paper is an extended abstract of the paper on arXiv hal-00339049, which contains all detailed proofs.</footnote>
## 1.1 Background

The linear extensions of posets contain very interesting subsets of the symmetric group: for example, the linear extensions of the poset considered in the article (3) are the permutations smaller than a permutation $\pi$ for the weak Bruhat order. In this case, our construction is close to that of Demazure characters (4). S. Butler and M. Bousquet-Mélou characterize the permutations $\pi$ corresponding to acyclic posets, which are exactly the cases where the function we consider is the simplest.

Moreover, linear extensions are hidden in a recent formula for irreducible character values of the symmetric group: if we use the notations of (7), the quantity $N^{\lambda}(G)$ can be seen as a sum over the linear extensions of the bipartite graph $G$ (bipartite graphs are a particular case of oriented graphs). This explains the similarity of the combinatorics in article (6) and in this one.

The function $\Psi_P$ was considered by C. Greene (8), who wanted to generalize a rational identity linked to Murnaghan-Nakayama rule for character values of the symmetric group. He has given in his article a closed formula for planar posets ($\mu_P$ is the Möbius function of $P$):

$$ \Psi_P = \begin{cases} 0 & \text{if } P \text{ is not connected,} \\ \prod_{y,z \in P} (x_y - x_z)^{\mu_P(y,z)} & \text{if } P \text{ is connected,} \end{cases} $$

However, there is no such formula for general posets, only the denominator of the reduced form of $\Psi_P$ is known (see article (2)). In this paper, the first author has investigated the effects of elementary transformations of the Hasse diagram of a poset on the numerator of the associated rational function. He has also noticed, that in some case, the numerator is a Schur function (2, paragraph 4.2) (we can also find Schubert polynomials or sums of multiSchur functions).

In this paper, we obtain some new results on this numerator, thanks to a simple local transformation in the graph algebra, preserving linear extensions.

## 1.2 Main results

**An inductive algorithm** The first main result of this paper is an induction relation on linear extensions (Theorem 3.1). When one applies $\Psi$ on it, it gives an efficient algorithm to compute the numerator of the reduced fraction of $\Psi_P$ (the denominator is already known).

**A combinatorial formula** If we iterate our first main result in a clever way, we can describe combinatorially the final result. The consequence is our second main result: if we give to the graph of a poset $P$ a rooted map structure, we have a combinatorial non-inductive formula for the numerator of $\Psi_P$ (Theorem 3.7).

**A condition for $\Psi_P$ to factorize** Green formula's for the function associated to a planar poset is a quotient of products of polynomials of degree 1. In the non-planar case, the denominator is still a product of degree 1 terms, but not the numerator. So we may wonder when the numerator $N(P)$ can be factorized.

Our third main result is a partial answer (a sufficient but not necessary condition) to this question: the numerator $N(P)$ factorizes if there is a chain disconnecting the Hasse diagram of $P$ (see Theorem 3.8 for a precise statement). An example is drawn on figure 1 (the disconnecting chain is
function can be easily formulated directly in terms of graphs (paragraphs 2.2 and 2.3).

We will also define some elementary removal operations on graphs (paragraph 2.4), which will be used in the next section. Due to transitivity relations, it is not equivalent to perform these operation on the Hasse diagram or on the complete graph of a poset, that's why we prefer to formulate everything in terms of graphs.

## 2.1 Definitions and notations on graphs

In this paper, we deal with finite directed graphs. So we will use the following definition of a graph G:

* A finite set of vertices $V_G$.

* A set of edges $E_G$ defined by $E_G \subset V_G \times V_G$.

If $e \in E_G$, we will note by $\alpha(e) \in V_G$ the first component of $e$ (called *origin of $e$*) and $\omega(e) \in V_G$ its second component (called *end of $e$*). This means that each edge has an orientation.

Let $e = (v_1, v_2)$ be an element of $V_G \times V_G$. Then we denote by $\bar{e}$ the pair $(v_2, v_1)$.

With this definition of graphs, we have four definitions of injective walks on the graph.

<table><thead><tr><th></th><th>can not go backwards</th><th>can go backwards</th></tr></thead><tbody><tr><th>closed</th><td>circuit</td><td>cycle</td></tr><tr><th>non-closed</th><td>chain</td><td>path</td></tr></tbody></table>

More precisely,

**Definition 2.1** Let G be a graph and E its set of edges.

**chain** A chain is a sequence of edges $c = (e_1, \dots, e_k)$ of G such that $\omega(e_1) = \alpha(e_2), \omega(e_2) = \alpha(e_3), \dots$ and $\omega(e_{k-1}) = \alpha(e_k)$.

**circuit** A circuit is a chain $(e_1, \dots, e_k)$ of G such that $\omega(e_k) = \alpha(e_1)$.

**path** A path is a sequence $(e_1, \dots, e_h)$ of elements of $E \cup \bar{E}$ such that $\omega(e_1) = \alpha(e_2), \omega(e_2) = \alpha(e_3), \dots$ and $\omega(e_{k-1}) = \alpha(e_k)$.

**cycle** A cycle C is a path with the additional property that $\omega(e_k) = \alpha(e_1)$. If C is a cycle, then we denote by $E(C)$ the set $C \cap E$.

In all these definitions, we add the condition that all edges and vertices are different (except of course, the equalities in the definition).

**Remark 1** The difference between a cycle and a circuit (respectively a path and a chain) is that, in a cycle (respectively in a path), an edge can appear in both directions (not only in the direction given by the graph structure). The edges, which appear in a cycle C with the same orientation than their orientation in the graph, are exactly the elements of $E(C)$.

To make the figures easier to read, $\alpha(e)$ is always the left-most extremity of $e$ and $\omega(e)$ its right-most one. Such drawing construction is not possible if the graph contains a circuit. But its case will not be very interesting for our purpose.
<figure><img src="image_2.png" /><figcaption>Fig. 3: Example of a chain and a cycle C (we recall that orientations are from left to right).</figcaption></figure>

**Example 1** An example of graph is drawn on figure 3. In the left-hand side, the non-dotted edges form a chain c, whereas, in the right-hand side, they form a cycle C, such that $E(C)$ contains 3 edges: (1, 6), (6, 8) and (5, 7).

The *cyclomatic number* of a graph G is $|E_G| - |V_G| + c_G$, where $c_G$ is the number of connected components of G. A graph contains a cycle if and only if its cyclomatic number is not 0 (see (5)). If it is not the case, the graph is called *forest*. A connected forest is, by definition, a tree. Beware that, in this context, there are no rules for the orientation of the edges of a tree (often, in the literature, an oriented tree is a tree which edges are oriented from the *root* to the *leaves*, but we do not consider such objects here).

## 2.2 Posets, graphs, Hasse diagrams and linear extensions

In this paragraph, we recall the link between graphs and posets.

Given a graph G, we can consider the binary relation on the set $V_G$ of vertices of G:

$$x \le y \iff \left( x = y \text{ or } \exists e \in E_G \text{ such that } \begin{cases} \alpha(e) = x \\ \omega(e) = y \end{cases} \right)$$

This binary relation can be completed by transitivity. If the graph has no circuit, the resulting relation $\le$ is antisymmetric and, hence, endows the set $V_G$ with a poset structure, which will be denoted $\text{poset}(G)$.

The application poset is not injective. Among the pre-images of a given poset $\mathcal{P}$, there is a minimum one (for the inclusion of edge set), which is called Hasse diagram of $\mathcal{P}$.

The definition of linear extensions given in the introduction can be formulated in terms of graphs:

**Definition 2.2** A linear extension of a graph G is a total order $\le_w$ on the set of vertices V such that, for each edge e of G, one has $\alpha(e) \le_w \omega(e)$.

The set of linear extensions of G is denoted $\mathcal{L}(G)$. Let us also define the formal sum $\varphi(G) = \sum_{w \in \mathcal{L}(G)} w$.

We will often see a total order $\le_w$ defined by $v_{i_1} \le_w v_{i_2} \le_w \dots \le_w v_{i_n}$ as a word $w = v_{i_1}v_{i_2}\dots v_{i_n}$.

**Remark 2** If G contains a circuit, then it has no linear extensions. Else, its linear extensions are the linear extensions of $\text{poset}(G)$. Thus considering graphs instead of posets does not give more general results.
## 2.3 Rational functions on graphs

Given a graph $G$ with $n$ vertices $v_1, \dots, v_n$, we are interested in the following rational function $\Psi_G$ in the variables $(x_{v_i})_{i=1\dots n}$: $$ \Psi_G = \sum_{w \in \mathcal{L}(G)} \frac{1}{(x_{w_1} - x_{w_2}) \dots (x_{w_{n-1}} - x_{w_n})} $$

We also consider the renormalization: $N(G) := \Psi_G \cdot \prod_{e \in E_G} (x_{\alpha(e)} - x_{\omega(e)})$.

The following properties of $N(G)$ have been proved in (2): the value of $N$ on forests is essential in the next section because we will compute $N$ by induction on the cyclomatic number.

**Lemma 2.1 (Pruning-invariance)** Let $G$ be a graph with a vertex $v$ of valence 1 and $e$ the edge of extremity (origin or end) $v$. Then one has $N(G) = N(G\{v\})$.

**Proposition 2.2** If $T$ is a tree, $N(T) = 1$. If $F$ is a disconnected forest, $N(F) = 0$.

## 2.4 Removing edges and vertices in graphs

The main tool of this paper consists in removing some edges of a graph $G$.

**Definition 2.3** Let $G$ be a graph and $E'$ a subset of its set of edges $E_G$. We will denote by $G\setminus E'$ the graph $G'$ with

* the same set of vertices as $G$;

* the set $E_{G'} := E_G \setminus E'$ as set of edges.

**Definition 2.4** If $G$ is a graph and $V'$ a subset of its set of vertices $V$, $V'$ has an induced graph structure: its edges are exactly the edges of $G$, which have both their extremities in $V'$.

If $V \setminus V' = \{v_1, \dots, v_l\}$, this graph will be denoted by $G \setminus \{v_1, \dots, v_l\}$. The symbol is the same than in definition 2.3, but it should not be confusing.

# 3 Computation and properties of the numerator

In the previous section, we have defined a simple operation on graphs consisting in removing edges. Thanks to this operation, we will be able to construct an operator which lets invariant the formal sum of linear extensions (paragraph 3.1). Due to the definition of $\Psi$, this implies immediately an inductive relation on the rational functions $\Psi_G$ (paragraph 3.2).

In paragraph 3.3, we solve the induction and obtain an additive formula for $N(G)$. But this formula has never a factorized form (even in the planar case), so we give in the last paragraph (3.4) a simple graphical condition which implies the partial factorization of $N(G)$.

## 3.1 Equality on linear extensions

In this paragraph, we prove an induction relation on the formal sums of linear extensions of graphs. More exactly, we write, for any graph $G$ with at least one cycle, $\varphi(G)$ as a linear combination of $\varphi(G')$, where $G'$ runs over graphs with a strictly lower cyclomatic number. In the next paragraphs, we will iterate this relation and apply $\Psi$ to both sides of the equality to study $\Psi_G$.
<figure><img src="image_3.png" /><figcaption>Fig. 4: Example of application of theorem 3.1</figcaption></figure>

If $G$ is a finite graph and $C$ a cycle of $G$, let us denote by $T_C(G)$ the following formal alternate sum of subgraphs of $G$:

$$T_C(G) = \sum_{\substack{E' \subset E(C) \\ E' \neq \emptyset}} (-1)^{|E'|-1} G \setminus E'$$

The function $\varphi(G) = \sum_{w \in \mathcal{L}(G)} w$ can be extended by linearity to the free abelian group spanned by graphs. One has the following theorem:

**Theorem 3.1** Let $G$ be a graph and $C$ a cycle of $G$ then, $\varphi(G) = \varphi(T_C(G))$.

An example is drawn on figure 4 (to make it easier to read, we did not write the operator $\varphi$ in front of each graph).

**Remark 3** In the case where $E(C) = \emptyset$, this theorem says that a graph with a circuit has no linear extensions (see remark 2).

If it is a singleton, it says that we do not change the set of linear extensions by erasing an edge if there is a chain going from its origin to its end (thanks to transitivity).

To prove Theorem 3.1, we will need the two following lemmas:

**Lemma 3.2** Let $w \in \mathcal{L}(G \setminus E(C))$. There exists $E'(w) \subset E(C)$ such that

$$\forall E'' \subset E(C), \quad w \in \mathcal{L}(G \setminus E'') \iff E'(w) \subset E'' \subset E(C).$$
**Proof:** Left to the conscientious reader.

□

**Lemma 3.3** Let $w \in \mathcal{L}(G\setminus E(C))$, there exists $E'' \subsetneq E(C)$ such that $w \in \mathcal{L}(G\setminus E'')$.

**Proof:** Suppose that we can find a word $w$ for which the lemma is false. Since $w \in \mathcal{L}(G\setminus E(C))$, the word $w$ fulfills the relations given by the edges of $G$, which are not in $E(C)$.

But, if $e \in E(C)$, one has $w \notin \mathcal{L}(G\setminus(E(C)\setminus\{e\}))$. That means that $w$ does not fulfill the relation corresponding to the edge $e$. As $w$ is a total order, it fulfills the opposite relation: $w \in \mathcal{L}[(G\setminus E(C)) \cup \{\bar{e}\}]$. With the same argument applied for each $e \in E(C)$, one has $w \in \mathcal{L}[(G\setminus E(C)) \cup \overline{E(C)}]$. But this graph contains a circuit, so its set of linear extension is empty. □

Let us come back to the proof of Theorem 3.1. Let $w$ be a word containing exactly once each element of $V_G$. We will compute its coefficient in $\varphi(G) - \varphi(T_C(G)) = \sum_{E' \subset E(C)} (-1)^{|E'|} \varphi(G\setminus E')$:

* If $w \notin \mathcal{L}(G\setminus E(C))$, its coefficient is zero in each summand.

* If $w \in \mathcal{L}(G\setminus E(C))$, thanks Lemma 3.2, we know that there exists $E'(w) \subset E(C)$ such that

$$ \forall E'' \subset E(C), w \in \mathcal{L}(G\setminus E'') \iff E'(w) \subset E'' \subset E(C). $$

So the coefficient of $w$ in $\varphi(G) - \varphi(T_C(G))$ is $\sum_{E'(w) \subset E'' \subset E(C)} (-1)^{|E''|} = 0$ because $E'(w) \neq E(C)$ (Lemma 3.3).

## 3.2 Consequences on rational functions

In the previous paragraph, we have established an induction formula for the formal sum of linear extensions (Theorem 3.1). One can apply $\Psi$ to both sides of this equality to compute $N(G)$:

**Proposition 3.4** Let $G$ be a graph containing a cycle $C$. Then,

$$ N(G) = \sum_{\substack{E' \subset E(C) \\ E' \neq \emptyset}} \left[ (-1)^{|E'|-1} N(G\setminus E') \prod_{e \in E'} (x_{\alpha(e)} - x_{\omega(e)}) \right]. $$

By Proposition 2.2, one has $N(T) = 1$ if $T$ is a tree and $N(F) = 0$ if $F$ is a disconnected forest. So this Proposition gives us an algorithm to compute $N(G)$: we just have to iterate it with any cycles until all the graphs in the right hand side are forests. More precisely, if after iterating transformations of type $T_C$ on $G$, we obtain the formal linear combination $\sum c_F F$ of subforests of $G$, then:

$$ N(G) = \sum_{T \text{ subtree of } G} c_T \prod_{e \in E_G \setminus E_T} (x_{\alpha(e)} - x_{\omega(e)}). $$

In this formula, $N(G)$ appears as a sum of polynomials. So the computation of $N(G)$, using this formula, is easier than a direct application of the definition

$$ N(G) = \sum_{w \in \mathcal{L}(G)} \left( \Psi_w \cdot \prod_{e \in E_G} (x_{\alpha(e)} - x_{\omega(e)}) \right), $$
where the summands may have poles.

**Corollary 3.5** For any graph $G$, the rational function $N(G)$ is a polynomial. Moreover, if $G$ is disconnected, $N(G) = 0$.

In fact, if a connected graph $G$ is the Hasse diagram of poset, the fraction $\Psi_G = \frac{N(G)}{\prod_{e \in E_G} (x_{\alpha(e)} - x_{\omega(e)})}$ is irreducible (see (2) for a proof of this fact).

**Example 2 (explicit computation)** Let $G_{2,4}$ be the graph with a set of vertices $V$ partitioned in two subsets $V_1 = \{a_1, a_2\}$ and $V_2 = \{b_1, b_2, b_3, b_4\}$ and $E = V_1 \times V_2$ as set of edges. After iterating Theorem 3.1, we obtain the equality of Figure 5 (the operator $\varphi$ has been once again omitted).

<figure><img src="image_4.png" /><figcaption>Fig. 5: Decomposition of $\varphi(G_{2,4})$.</figcaption></figure>

$$ \text{Thus, } N(G_{2,4}) = \sum_{i=1}^{4} \left( \prod_{j<i} (b_j - a_1) \cdot \prod_{k>i} (b_k - a_2) \right). $$

## 3.3 A combinatorial formula for $N$

To compute the polynomial $N$ of a graph $G$, we only have to find the coefficient of trees in a formal linear combination of forests obtained by iterating transformations $T_C$ on $G$. But there are many possible choices of cycle at each step and these coefficients depend on these choices.

A way to avoid this problem is to give to $G$ a rooted map structure $M$ and to look at the particular decomposition $D(M)$ introduced in the paper (6, section 3). We will not describe here this particular choice of cycles (see the complete version), but we have a combinatorial description of the trees with coefficient +1 in $D(M)$, all other trees having 0 as coefficient.

**Definition 3.1** A (combinatorial oriented) map is a connected graph with, for each vertex $v$, a cyclic order on the edges whose origin or end is $v$. This definition is natural when the graph is drawn on a two dimensional surface (see for example (10)).

It is more convenient when we deal with maps, to consider edges as couples of two darts $(h_1, h_2)$, the first one of extremity $\alpha(e)$ and the second one of extremity $\omega(e)$. A rooted map is a map with an external dart $h_0$, that is to say a dart which do not belong to any edge, but has an extremity and a place in the cyclic order given by this extremity.

We will need the following definition:

**Definition 3.2** If $T$ is a spanning subtree of a rooted map $M$, the tour of the tree $T$ beginning at $h_0$ defines an order on the darts which do not belong to $T$. The definition is easy to understand on a figure: for example, on Figure 6, the tour is $h_1^1, h_2^1, h_1^2, h_2^2, h_1^3, h_1^4, h_2^3, h_2^4$ (see (1) for a precise definition).
<figure><img src="image_5.png" /><figcaption>Fig. 6: Tour of a spanning tree of a rooted map.</figcaption></figure>

We are now able to describe the coefficients of trees in D(M):

**Proposition 3.6** Let M be a rooted map and T a spanning tree of M.

• If there is an edge e = (h₁, h₂) ∈ M \ T such that h₂ appears before h₁ in the tour of T, then the coefficient of T in D(M) is 0.

• Else, the coefficient of T in D(M) is +1 (in this case, T is said to be good).

For example, the spanning tree of Figure 6 is good. Note that the property of being a good spanning tree does not depend on the orientations of the edges of the tree, but only on the orientations of those which do not belong to it.

This Proposition is not very hard to prove, once we have the good definition of D(M), but the latter is quite technical and requires a non-easy proof of confluence. As an immediate consequence of the proposition, we have the following formula for N(G):

**Theorem 3.7** The polynomial N associated to the underlying graph G of a rooted map M is given by the following combinatorial formula:

$$
N(G) = \sum_{T \text{ good spanning tree of } M} \left[ \prod_{e \in E_G \setminus E_T} (x_{\alpha(e)} - x_{\omega(e)}) \right]. \qquad (1)
$$

3.4 Chain factorization

In the previous paragraph, we have given an additive formula for the numerator of the reduced fraction of Ψ<sub>P</sub>. Green formula for planar posets (see subsection 1.1) and the example of Figure 1 show that, in
some cases, it can also be written as a product. In this paragraph we give a simple graphical condition on a graph $G$, which implies the factorization of $N(G)$.

**Remark 4** In this section, we assume that $G$ has no circuit and no transitivity relation (an edge going from the beginning to the end of a chain). This is always true in the case of Hasse diagrams of posets so we do not lose in generality. With this assumption, if we consider a chain $c$, there is no extra edges between the vertices of the chain.

Let $G$ be a connected graph, $c$ a chain of $G$, $V_c$ the set of vertices of $c$ (including the origin and the end of the chain) and $G_1, \dots, G_k$ be all the connected components of $G \setminus V_c$. The complete subgraphs $\overline{G}_i = G_i \cup V_c$ (for $1 \le i \le k$) will be called regions of $G$. An example (with $k=4$) is drawn on Figure 7 (we consider the chain with $V_c = \{1, 2, 13, 3, 4, 5, 6, 14\}$).

<figure><img src="image_6.png" /><figcaption>**Fig. 7:** A graph $G$ with a chain $c$, the connected components $G_i$ of $G \setminus V_c$ and the corresponding regions $\overline{G}_i$.</figcaption></figure>

We can now state our third main result:

**Theorem 3.8** Let $G$ be a connected graph, $c$ a chain of $G$ and $\overline{G_1}, \overline{G_2}, \dots, \overline{G_k}$ be the corresponding regions of $G$. Then one has:

$$N(G) = \prod_{j=1}^{k} N(\overline{G_j}).$$

In the example 7, the numerator $N(G)$ can be factorized into four non-trivial factors. This theorem is proved in the complete version of the paper. It relies on a clever application of Proposition 3.4 and is a little technical.

In the case of planar posets considered by Greene (8), this theorem explains the fact that the numerator of the associated rational function is a product of polynomials of degree 1. We can even give a new proof
<figure><img src="image_7.png" /><figcaption>Fig. 8: A non-planar (with Greene's definition) poset for which Greene's formula is true.</figcaption></figure>

of Greene's formula (stated in subsection 1.1), which works in a context a little more general than planar posets (see Figure 8).

## Acknowledgements

The authors are grateful to A. Lascoux for his suggestion to work on this rational functions.

## References

[1] O. Bernardi, A characterization of the Tutte polynomial via combinatorial embedding, Annals of Combinatorics, Vol 12(2), pp 139-153 (2008).

[2] A. Boussicault, *Operations on Posets and Rational Identities of Type A*. Poster session of 19th Formal Power Series and Algebraic Combinatorics (2007).

[3] M. Bousquet-Mélou and S. Butler, Forest-like permutations, Annals of Combinatorics 11 (2007) 335-354.

[4] M. Demazure, Une nouvelle formule des caractères, Bull. Sci. Math., 98 (1974) 163-172.

[5] R. Diestel, Graph Theory, Graduate Texts in Mathematics 173 (2005), Springer-Verlag Heidelberg.

[6] V. Féray, Combinatorial interpretation and positivity of Kerov's character polynomials, Journal of Algebraic Combinatorics, (2008) to appear.

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

[8] C. Greene, A rational function identity related to the Murnaghan-Nakayama formula for the characters of $S_n$, J. Alg. Comb. 1 3 (1992), 235-255.

[9] A. Lascoux, *Schubert and MacDonald polynomials, a parallel*, preprint (2008), available online: www.igm.univ-mlv.fr/~al/ARTICLES/MsriExp.pdf

[10] W. T. Tutte, *A census of planar map*, Canad. J. Math. 14, (1963) 21-38.