Application of graph combinatorics to rational identities of type A.

1 Introduction

A partially ordered set (poset) V 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 V (if a [greater than or equal to] p b, then a must be before b in w). To a linear extension w = [v.sub.1] [v.sub.2] ... [v.sub.n], we associate a rational function:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We can now introduce the main object of the paper. If we denote by L(P) the set of linear extensions of P, then we define [[PSI].sub.p] by:

[[PSI].sub.p] = [summation over (w [member of]L(P))] [[psi].sub.w].

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-Melou 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.sup.[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].sub.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].sub.p] is the Mobius function of P):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

However, there is no such formula for general posets, only the denominator of the reduced form of [[PSI].sub.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].sub.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].sub.p] (Theorem 3.7).

A condition for [[PSI].sub.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 (2,5)). Note that we use here and in the whole paper a unusual convention: we draw the posets from left (minimal elements) to right (maximal elements).

[FIGURE 1 OMITTED]

1.3 Open problems

Necessary condition for factorization The conclusion of the factorization Theorem 3.8 is sometimes true, even when the separating path is not a chain: see for example Figure 2 (the path (5, 6, 3) disconnects the Hasse diagram, but is not a chain).

This equality, and many more, can be easily proved using the same method as Theorem 3.8. Can we give a necessary (and sufficient) condition for the numerator of a poset to factorize into a product of numerators of subposets? Are all factorizations of this kind?

Characterization of the numerator Let us consider a poset P, which has only minimal and maximal elements (respectively [a.sub.1], ..., [a.sub.l] and [b.sub.1], ..., [b.sub.r]). The numerator N(P) of [[PSI].sub.p] is a polynomial in [b.sub.1], ..., [b.sub.r] which degree in each variable can be easily bounded (2, Proposition 3.1). Thanks to Proposition 3.4, we see immediately that N(P) = 0 on some affine subspaces of the space of variables. Unfortunately, these vanishing relations and its degree do not characterize N(P) up to a multiplicative factor. Is there a bigger family of vanishing relations, linked to the combinatorics of the Hasse diagram of the poset, which characterizes N(P)?

This question comes from the following observation: for some particular posets, the numerator is a Schubert polynomial and Schubert polynomials are known to be easily defined by vanishing conditions (9).

2 Graphs, posets and rational functions

Oriented graphs are a natural way to encode information of posets. To avoid confusions, we recall all necessary definitions in paragraph 2.1. The definition of linear extensions and hence of our rational 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.

[FIGURE 2 OMITTED]

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.sub.G].

* A set of edges [E.sub.G] defined by [E.sub.G] [subset] [V.sub.G] x [V.sub.G].

If e [member of] [E.sub.G], we will note by [alpha](e) [member of] [V.sub.G] the first component of e (called origin of e) and [omega](e) [member of] [V.sub.G] its second component (called end of e). This means that each edge has an orientation. Let e = ([v.sub.1], [v.sub.2]) be an element of [V.sub.G] x [V.sub.G]. Then we denote by [bar.e] the pair ([v.sub.2], [v.sub.1]).

With this definition of graphs, we have four definitions of injective walks on the graph.
```             can not go backwards   can go backwards

closed             circuit               cycle
non-closed          chain                 path
```

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.sub.1], ..., [e.sub.k]) of G such that [omega]([e.sub.1]) = [alpha]([e.sub.2]), [omega]([e.sub.2]) = [alpha]([e.sub.3]), ... and [omega]([e.sub.k-1]) = [alpha]([e.sub.k]).

circuit A circuit is a chain ([e.sub.1], ..., [e.sub.k]) of G such that [omega]([e.sub.k]) = [alpha]([e.sub.1]).

path A path is a sequence ([e.sub.1], ..., [e.sub.h]) of elements of E [union] [bar.E] such that [omega]{[e.sub.1]) = [alpha]([e.sub.2]), [omega]([e.sub.2]) = [alpha] ([e.sub.3]), ... and [omega]([e.sub.k-1]) = [alpha] ([e.sub.k]).

cycle A cycle C is a path with the additional property that [omega]([e.sub.k]) = [alpha]([e.sub.1]). If C is a cycle, then we denote by E(C) the set C [intersection] 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 3 OMITTED]

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 [absolute value of [E.sub.G]] - [absolute value of [V.sub.G]] + [c.sub.G], where [c.sub.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.sub.G] of vertices of G:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This binary relation can be completed by transitivity. If the graph has no circuit, the resulting relation [less than or equal to] is antisymmetric and, hence, endows the set [V.sub.G] with a poset structure, which will be denoted poset(G).

The application poset is not injective. Among the pre-images of a given poset P, there is a minimum one (for the inclusion of edge set), which is called Hasse diagram of 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 [[less than or equal to].sub.w] on the set of vertices V such that, for each edge e of G, one has [alpha](e) [[less than or equal to].sub.w] [omega](e).

The set of linear extensions of G is denoted L(G). Let us also define the formal sum [phi](G) = [summation over (w [member of] L(G))] w.

We will often see a total order [[less than or equal to].sub.w] defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as a word [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Remark 2 If G contains a circuit, then it has no linear extensions. Else, its linear extensions are the linear extensions of 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.sub.1], ..., [v.sub.n], we are interested in the following rational function [[PSI].sub.G] in the variables [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We also consider the renormalization: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

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.sub.G]. We will denote by G\E' the graph G' with

* the same set of vertices as G;

* the set [E.sub.G'] := [E.sub.G]\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\V' = {[v.sub.1], ..., [v.sub.l]}, this graph will be denoted by G\{[v.sub.1], ..., [v.sub.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].sub.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, [phi](G) as a linear combination of [phi](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].sub.G].

[FIGURE 4 OMITTED]

If G is a finite graph and C a cycle of G, let us denote by [T.sub.C](G) the following formal alternate sum of subgraphs of G:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The function [phi](G) = [summation over (w [member of]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, [phi](G) = [phi]([T.sub.C](G)).

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

Remark 3 In the case where E(C) = 0, 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 lemma:

Lemma 3.2 Let w [member of] L(G\E(C)). There exists E'(w) [subset] E(C) such that

[for all]E" [subset] E(C), w [member of] L(G\E") [??] E'(w) [subset] E" [subset] E(C).

Proof: Left to the conscientious reader.

Lemma 3.3 Let w [member of] C(G\E(C)), there exists E" [??] E(C) such that w [member of] L(G\E").

Proof: Suppose that we can find a word w for which the lemma is false. Since w [member of] L(G\E(C)), the word w fulfills the relations given by the edges of G, which are not in E(C).

But, if e [member of] E(C), one has w [not member of] L(G\(E(C)\{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 [member of] C [(G\E(C)) [union] {[bar.e]}]. With the same argument applied for each e [member of] E(C), one has w [member of] L [(G\E(C)) [union] [bar.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.sub.G]. We will compute its coefficient in [phi](G) - [phi]([T.sub.C](G)) = [[summation].sub.E'[subset]E(C)] [(- 1).sup.[absolute value of E']] [phi](G\E'):

* If w [not member of] L(G\E(C)), its coefficient is zero in each summand.

* If w [member of] L(G\E(C)), thanks Lemma 3.2, we know that there exists E'(w) [subset] E(C) such that

[for all]E" [subset] E(C),w [member of] L(G\E") [??] E'(w) [subset] E" [subset] E(C).

So the coefficient of w in [phi](G) - [phi]([T.sub.C](G)) is [summation over (E'(w)[subset]E"[subset]E(C))] [(-1).sup.[absolute value of E"]] = 0 because E'(w) [not equal to] 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 * to both sides of this equality to compute N(G):

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

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

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.sub.C] on G, we obtain the formal linear combination [summation] [c.sub.F] F of subforests of G, then:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

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

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

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 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is irreducible (see (2) for a proof of this fact).

Example 2 (explicit computation) Let [G.sub.2,4] be the graph with a set of vertices V partitioned in two subsets [V.sub.1] = {[a.sub.1], [a.sub.2]} and [V.sub.2] = {[b.sub.1], [b.sub.2], [b.sub.3], [b.sub.4]} and E = [V.sub.1] x [V.sub.2] as set of edges. After iterating Theorem 3.1, we obtain the equality of Figure 5 (the operator [phi] has been once again omitted).

[FIGURE 5 OMITTED]

Thus, N([G.sub.2,4]) = [[summation].sup.4.sub.i=1] ([[PI].sub.j<i] ([b.sub.j] - [a.sub.i]) * [[PI].sub.k>i] ([b.sub.k] - [a.sub.2])).

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.sub.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.sub.1], [h.sub.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.sub.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.sub.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.sup.1.sub.1], [h.sup.1.sub.2], [h.sup.2.sub.1], [h.sup.2.sub.2], [h.sup.3.sub.1], [h.sup.4.sub.1], [h.sup.3.sub.2], [h.sup.2.sub.4] (see (1) for a precise definition).

[FIGURE 6 OMITTED]

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.sub.1], [h.sub.2]) [member of] M\T such that [h.sub.2] appears before [h.sub.1] 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:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

3.4 Chain factorization

In the previous paragraph, we have given an additive formula for the numerator of the reduced fraction of [[PSI].sub.P]. 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.sub.c] the set of vertices of c (including the origin and the end of the chain) and [G.sub.1], ..., [G.sub.k] be all the connected components of G [V.sub.c]. The complete subgraphs [G.sub.i] = [G.sub.i] [union] [V.sub.c] (for 1 [less than or equal to] i [less than or equal to] k) will be called regions of G. An example (with k = 4) is drawn on Figure 7 (we consider the chain with [V.sub.c] = {1, 2, 13, 3, 4, 5, 6, 14}).

[FIGURE 7 OMITTED]

We can now state our third main result:

Theorem 3.8 Let G be a connected graph, c a chain of G and [bar.[G.sub.1]], [bar.[G.sub.2]], ..., [bar.[G.sub.k]] be the corresponding regions of G. Then one has:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

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 of Greene's formula (stated in subsection 1.1), which works in a context a little more general than planar posets (see Figure 8).

[FIGURE 8 OMITTED]

Acknowledgements

The authors are grateful to A. Lascoux for his suggestion to work on these 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-Melou and S. Butler, Forest-like permutations, Annals of Combinatorics 11 (2007) 335-354.

[4] M. Demazure, Une nouvelleformule des caracteres, Bull. Sci. Math., 98 (1974) 163-172.

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

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

[7] V. Feray and P. Sniady. 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.sub.n], J. Alg. Comb. 1 3 (1992), 235-255.

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

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

Adrien Boussicault (1) and Valentin Feray (1)

(1) Universite Paris-Est, Institut d'eiectronique et d'informatique Gaspard-Monge, 77454 Marne-la-Valiee Cedex 2

* This paper is an extended abstract of the paper on arXiv 0811.2562, which contains all detailed proofs.