Printer Friendly

On the ranks of configurations on the complete graph.

We consider the following solitary game on an undirected connected graph with no loops: at the beginning a configuration u is given, meaning that integer values [u.sub.i] are attributed to the n vertices [x.sub.1], [x.sub.2], ... [x.sub.n] of the graph. These values can be positive or negative. At each step a toppling can be performed by the player on a vertex [x.sub.i]: it consists in subtracting [d.sub.i] (the number of neighbors of [x.sub.i]) to the amount uj and adding 1 to all the amounts [u.sub.j] of the neighbors [x.sub.j] of [x.sub.i]. In this operation the amount of vertex [x.sub.i] may become negative. The aim of the player is to find a sequence of toppling operations which will end with a configuration where all the [u.sub.i] are non negative. Since the sum deg(u) of the [u.sub.i] is invariant by the toppling, a necessary condition to succeed is that in the initial configuration deg(u) should be non negative.

This game has much to do with the chip firing game (see Bjorner et al. (1991), Biggs (1999)) and the sandpile model (see Bak et al. (1988), Dhar (1990), Dhar and Majumdar (1992)), for which recurrent configurations were defined and proved to be canonical representatives of the classes of configurations equivalent by a sequence of topplings.

The game was introduced and studied in detail by Baker and Norine (Baker and Norine (2007)) who introduced a new parameter on graph configurations: the rank. The rank [rho](u) of a configuration u is non negative if and only if one can get from u a positive configuration by performing a sequence of topplings. For this parameter they obtain a simple formula expressing a symmetry similar to the Riemann-Roch formula for surfaces (a classical reference to this formula is the book by Farkas and Kra (1992)).

Our aim here is to study the values of this parameter when G is the complete graph on n vertices, for these graphs it was noticed (see Proposition 2.8. in Cori and Rossin (2000)) that the recurrent configurations correspond to the parking functions which play a central role in combinatorics. We obtain a simple greedy algorithm to compute the rank in that case, expected to be of linear complexity after optimisation, while there is no known polynomial time algorithm to compute that rank for arbitrary graphs.

The distribution of rank and degree on a natural subset of configurations over a graph G, the parking ones, is a bivariate power series [P.sub.G](x, r) which has a symmetry inherited from the Riemann-Roch theorem. We show that some coefficients of these series are related to an evaluation of Tutte polynomial. In the case of complete graphs, we prove that our greedy algorithm to compute the rank has a linear complexity when assuming that arithmetic operations on the [u.sub.i] may be performed in constant time. Up to the classical action of symmetric group [S.sub.n] on configurations our algorithm may be described in terms of Dyck words. The analysis of this algorithm leads to the definition of a parameter on Dyck words, which will call prerank. We prove that the distribution of area and prerank on Dyck words of length 2n leads to a polynomial in two variables which is symmetric in these. This polynomial has some values in common with the q, t-Catalan polynomial studied in Garsia and Haiman (1996); Haglund (2008). We provide a bijective proof of the symmetry of our polynomial and propose an expression for it using Tchebychev polynomials. Moreover the bistatistic prerank and dinv leads to the q, t-Catalan polynomial.

1 Configurations on a graph

1.1 The Laplacian configurations

Let G = (X, E) be a multi-graph, where X = {[x.sub.1], [x.sub.2], ..., [x.sub.n]} is the vertex set and E is a symmetric matrix such that [e.sub.i,j] is the number of edges with endpoints [x.sub.i], [x.sub.j], hence [e.sub.i,j] = [e.sub.i,j]. In all this paper n denotes the number of vertices of the graph G and m the number of its edges. Moreover we suppose that G is connected and has no loops, so that [e.sub.i,j] = 0 for all i.

We will consider configurations on this graph, which are elements of the discrete lattice [Z.sup.n]. Each configuration u may be considered as assigning (positive or negative) tokens to the vertices. When there is no possibility of confusion the symbol [x.sub.i] will also denote the configuration in which the value 1 is assigned to vertex [x.sub.i] is and the value 0 is assigned to all others. Laplacian configurations [DELTA](i) given by: [[DELTA].sup.(i)] = [d.sub.i][x.sub.i] - [[summation].sup.n.sub.i=1] [e.sub.i,j][x.sub.j], where [d.sub.i] = [[summation].sup.n.sub.i=1][e.sub.i,j] is the degree of the vertex [x.sub.i], play a central role througout this paper.

The degree of the configuration u is the sum of the [u.sub.i]'s and is denoted deg(u). We denote by [L.sub.G] the subgroup of [Z.sup.n] generated by the [[DELTA].sup.(i)], and two configurations u and v will be said toppling equivalent if u - v [member of] [L.sub.G], which will also be written as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

1.2 Parking configurations

In each class of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] one configuration may be considered as a canonical representative. We call such configurations parking configurations since in the case of complete graphs, these are exactly the parking functions, a central object in combinatorics.

Definition 1 A configuration u on a graph G is a parking configuration if [u.sub.i] [greater than or equal to] 0 for i < n and for any subset Y of {[x.sub.1], [x.sub.2], ..., [x.sub.n-1]} there is a vertex [x.sub.i] in Y such that [u.sub.i] is less than the number of edges which have as endpoints [x.sub.i] and an [x.sub.j] not in Y. More precisely if there exists i such that [x.sub.i] [member of] Y and

In other words a configuration u is a parking configuration if and only if there is no toppling of all the vertices in a subset Y of {[x.sub.1], [x.sub.2], ... [x.sub.n-1]} leaving all the [u.sub.i] [greater than or equal to] 0.

Proposition 1 For any configuration u there exists a unique parking configuration denoted parking(u) such that u - parking(u) [member of] [L.sub.G]

The proof of this Proposition is based on the notion of recurrent configurations which was considered and characterized by D. Dhar, a simple proof of the the uniqueness of a recurrent configuration is given in Cori and Rossin (2000).

1.3 Parking configurations and acyclic orientations

An orientation of G is a directed graph obtained from G by orienting each edge, so that one end vertex is called the head and the other vertex is called the tail. A directed path in such a graph consists of a sequence of edges such that the head of an edge is equal to the tail of the subsequent one.

The orientation is acyclic if there is no directed circuit, i.e. a directed path starting and ending at the same vertex. We associate to any parking configuration u an acyclic orientation by:

Proposition 2 For any parking configuration u on G = (X, E) there exists an acyclic orientation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that for any vertex [x.sub.i], i [not equal to] n, [u.sub.i] is strictly less than its indegree [d.sup.-.sub.i].

Proof: We orient the edges using an algorithm that terminates after n steps. Consider Y = {[x.sub.1], [x.sub.2], ..., [x.sub.n-1]}. From the condition for parking configurations given above, there is one vertex [x.sub.i] such that [u.sub.i] < [e.sub.i,n] then orient all these [e.sub.i,n] edges from [x.sub.n] to [x.sub.i], and remove [x.sub.i] from Y. Repeat the following operation until Y is empty:

* Find [x.sub.k] in Y such that [u.sub.k] < [[summation].sub.xj[not member of]Y] [e.sub.k,j]; orient all the edges joining any vertex j outside Y to [x.sub.k] from [x.sub.j] to [x.sub.k] and remove [x.sub.k] from Y.

2 Effective configurations and rank

In this section we give the main results of Baker and Norine (2007).

Definition 2 A configuration u is positive if [u.sub.i] [greater than or equal to] 0 for all i. A configuration u is effective if there exists a positive configuration v such that u - v [member of] [L.sub.G].

Since two equivalent configurations by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] have the same degree, it is clear that a configuration with negative degree is not effective. However we will prove that configurations with positive degree are not necessarily effective as the two examples in Figure 1(a) show.

2.1 Configuration associated to an acyclic orientation of G

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be an acyclic orientation of G, we define the configuration u-G by: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the number of edges which have head [x.sub.i]. The configuration represented in Figure 1(b) is equal to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for the represented orientation of G.

Proposition 3 The configuration associated to an acyclic orientation of G is non effective.

2.2 Characterisation of effective configurations

Theorem 1 For any configuration u, one and only one of the following assertions is satisfied:

(1) u is effective.


Moreover u is effective if and only if the parking configuration v such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] satisfies [v.sub.n] [greater than or equal to] 0.

Corollary 1 Any configuration u with degree greater than m - n is effective.

Proof: If u such that deg(u) > m - n is not effective, by the above theorem there exists an acyclic orientation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is. But the degree of this configuration is negative, giving a contradiction.

2.3 The rank of configurations

From now on it will be convenient to denote positive configurations by using the letters f, g ... and configurations with no particular assumptions on them by the letters u, v, w.

Definition 3 The rank p(u) of a configuration is the integer defined by:

* If u is non effective it is equal to -1

* If u is effective, it is the largest integer r such that for any positive configuration f of degree r the configuration u - f is effective.

Denoting P as the set of positive configurations and E as the set of effective configurations, this definition can given by the following formula which is valid in both cases:

[rho](u)+ 1 = [min.sub.f[member of]P,u-f[not member of]E] deg(f).

An immediate consequence of this definition is that if deg(u) [greater than or equal to] -1 then [rho](u) [less than or equal to] deg(u), and for any acyclic orientation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the rank of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Moreover if two configurations u and v are such that [u.sub.i] [less than or equal to] [v.sub.i] for all i then [rho](u) [less than or equal to] [rho](v).

Definition 4 A positive configuration f is a proof for the rank p(u) of an effective configuration u if u - f is non effective and u - h is effective for any positive configuration h such that deg(h) < deg(f).

Notice that if f is a proof for [rho](u) then [rho](u) = deg(f) - 1 = deg(f) + [rho](u - f).

Proposition 4 A configuration u of degree greater than 2m - 2n has rank r such that

r + 1 = deg(u) - (m - n).

Proof: We first show that for any positive configuration f such that deg(f) = r, the configuration u - f is effective. This follows from deg(u - f) = deg(u) - r = m - n + 1 by Corollary 1.

We now build a positive configuration f of degree r + 1 such that u - f is not effective. Consider any acyclic orientation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then v is effective since its degree is equal to deg(u) - m + n and is therefore greater than m - n. Let f be the positive configuration such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then u - f is such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] so that u - f is not effective by Theorem 1.

This result can be generalized into the following theorem which was given in Baker and Norine (2007) and called the Riemann-Roch theorem for graphs. A geometric interpretation of it is given in Amini and Manjunath (2010) and used in Manjunath (2011).

Theorem 2 Let [kappa] be the configuration such that [[kappa].sub.i] = [d.sub.i] - 2 where for i = 1, ..., n, the value [d.sub.i] is the degree of the vertex [x.sub.i]. Then we have for any configuration u:

[rho](u) - [rho](k - u) = deg(u) - (m - n).

3 A greedy algorithm computing the rank for configurations on complete graphs

Configurations on the complete graph may be sorted in such a way that the first n - 1 components form a weakly decreasing sequence. Clearly any configuration and its sorted version have equal ranks. The algorithm for determining the rank of u that we will describe proceeds in a certain number of steps. Each of these steps consists in replacing u by a u', and it will be convenient to work on their sorted versions. From an algebraic point of view this consists in considering orbits of the action of the symmetric group [S.sub.n-1] on the first n - 1 components instead of mere configurations; the correctness of the computation is validated by the fact that all configurations in the same orbit have the same rank.

3.1 Greedy algorithm on parking functions

Any configuration u is toppling equivalent to a single parking configuration parking(u). In the case of the complete graph [K.sub.n] there is a linear time algorithm to compute it. It will be given below after developing the link between Dyck words and parking configurations. We first examine how to determine the rank of a parking configuration. On [K.sub.n], a configuration u is a parking one if and only if after sorting the first n - 1 entries one obtains v = ([v.sub.1], ... [v.sub.n-1], [u.sub.n]), satisfying 0 [less than or equal to] [v.sub.i] < n - i for any 1 [less than or equal to] i < n. In particular, [v.sub.n-1] = 0; so in any parking configuration at least one of the [u.sub.i]'s is equal to 0. Our greedy algorithm determines the rank of a configuration u on [K.sub.n] by iteratively computing the parking configuration v equivalent to u and subtracting 1 on one of the [v.sub.i] such [that.sup.(i)] [v.sub.i] = 0 until the resulting parking configuration is such that [u.sub.n] < 0. The rank is then equal to the number of iterations done, the algorithm is given in the left part of Figure 2.The fact that this algorithm correctly computes the rank is a consequence of the lemma below.

Fig. 2: Two versions of a greedy algorithm computing rank on
[K.sub.n]: on configurations and Dyck words.

1: u [left arrow] parking(u)

2: rank [left arrow] -1

3: while [u.sub.n] [greater than or equal to] 0 do

4: u [left arrow] subtract 1 in one of a [u.sub.i] such
  that [u.sub.i] = 0 and i < n

5: u [left arrow] parking(u)

6: rank [left arrow] rank + 1

7: end while

8: Return rank

1: u [left arrow] parking(u)

2: (d, s) [left arrow] (d(u), s(u))

3: rank [left arrow] -1

4: while s [greater than or equal to] 0 do

5: match d with a f bg

6: d [left arrow] gabf

7: rank [left arrow] rank + 1

8: s [left arrow] s - [[absolute value of a f b].sub.a]

9: end while

10: Return rank

Lemma 1 Any positive configuration u where u = 0 admits a proof g for its rank such that gi > 0.

Proof: Denote by [[epsilon].sup.(i)] the configuration where [e.sup.(i).sub.i] = 1 and for j [not equal to] i, [[epsilon].sup.(i).sub.j] = 0. Let f [greater than or equal to] 0 be a proof of [rho](u) and assume [f.sub.i] = 0, otherwise g = f satisfies the lemma. Let j [not equal to] i such that [u.sub.j] - [f.sub.j] = -a < 0. Let v = u - (f - a[[epsilon].sup.(j)]). Then 0 < f - a[[epsilon].sup.(j)] [less than or equal to] f - a[[epsilon].sup.(j)] and [v.sub.i] = 0 = [v.sub.j]. Let [tau] be the transposition which exchanges i and j. Since v = [tau]v, we have g = f - a[[epsilon].sup.(j)] + a[[epsilon].sup.(j)] satisfies [g.sub.i] > 0, hence it is positive and has the same degree as f. Moreover u - g is also non-effective since u - g = v - a[[epsilon].sup.(i)] = [tau].[v - a[[epsilon].sup.(j)]] = [tau](u - f), hence g is the proof of [rho](u) as required.

To prove the correctness of the algorithm it suffices to remark that it determines a proof g of the rank of u such that [g.sub.i] > 0.

3.2 Greedy algorithm on Dyck words

Let A be the alphabet with two letters {a, b}. For a word w on the alphabet A and for a letter x [member of] A, [[absolute value of w].sub.x] denotes the number of occurrences of x in w. The function [delta] on words is defined by: [delta](w) = [[absolute value of w].sub.a] - [[absolute value of w].sub.b]. A Dyck word w is a word on the alphabet {a, b} such that [delta](w) = 0, and for any of its prefixes w' one has [delta](w') [greater than or equal to] 0. The size of a Dyck word w is [[absolute value of w].sub.a] = [absolute value of w]/2. The height h(w') of a prefix w' ending by an a of a Dyck word w is given by: h(w') = [delta](w') - 1. The maximal height H(w) of a Dyck word w is h(w) = [max.sub.w'] h(w') where w' runs through all prefixes of w ending with a.

To any (sorted) configuration u of [K.sub.n] such that

n - 1 [greater than or equal to] [u.sub.1] [greater than or equal to] [u.sub.2] [greater than or equal to] ... [u.sub.n-1] [greater than or equal to] 0 (1)

we associate a word w = D(u) with n - 1 occurrences of a and n occurrences of b the following way: the ith occurrence of a in w has exactly [u.sub.n-i] occurrences of b before it; notice that D(u) ends with an occurrence of b. Moreover D(u) is a Dyck word followed by a b, if and only if u is a parking configuration. This leads to a reformulation of the preceding greedy algorithm in terms of Dyck words. When u is a sorted parking configuration it is convenient to write D(u) = d(u)b such that d(u) is a Dyck word.

Any non-empty Dyck word w admits the non-ambiguous classical first return decomposition w = a f bg where f and g are Dyck words. As announced at the beginning of this Section, we consider the algorithm computing the rank in terms of sorted parking configurations toppling equivalent to it and its image via the preceding map u [right arrow] D(u). The algorithm may be described in terms of Dyck words due to:

Proposition 5 For any sorted parking configuration u, one step of the algorithm computing the rank consists in the subtraction of 1 on [u.sub.n-1] and then computing the sorted parking configuration u' toppling equivalent to it. In terms of words, this translates to the following: if w = d(u) = a f bg is the first return decomposition of u then the new value of w is d(u') = gabf.

The algorithm is described in detail in the right part of Figure 2. We do not provide a detailed proof of roposition 5 in this extended abstract, however we give details on an example of a loop iteration.

Assume that the algorithm reaches the sorted parking configuration u = (5, 4, 4, 2, 0, 0, 0, s) for some s [greater than or equal to] 0, also described by (d(u), s(u)) = (aaabbabbaababb, s). We draw d(u) in red from south- east to north-west in part (a) of Figure 3 above. This red path and the brown horizontal axis pointed by [??] 0 define the diagram of the partition ([u.sub.1], ... [u.sub.n-1]) in which un is omitted. We observe the following iteration step: we subtract 1 to un-1 and to recover positivity the vertex [x.sub.n] is toppled to reach v = (6, 5, 5, 3, 1, 1, 0, s - 7). These two steps are represented in part (b) of Figure 3. The cell labeled by r describes the removed token and then the brown horizontal axis is lowered by one unit, adding one cell labeled by s on each column of the partition which is the token coming from the toppling of the sink. This configuration v is not parking since the three first vertices may topple together, preserving positivity. On (b), observe that it corresponds to the rightmost vertical cross of the red path with the brown diagonal, this should not be crossed if the configuration was a parking one. The toppling of the three first vertices leads to w = (1, 0, 0, 6, 4, 4, 3, s - 4) is illustrated in part (c) of Figure 3. The tokens transmitted from these three toppled vertices to the four untoppled vertices different from [x.sub.n] may be interpreted as those in cells labeled by d in (b) (before toppling) and by cells on (c) labeled by i (after toppling). The configuration w is sorted to get w' = (6, 4, 4, 3, 1, 0, 0, s - 4) described in part (d), and this sorting may be interpreted as taking a conjugate of the word d(u). This sorting operation may also be also described by the exchange of f and g in the rewriting of afbg into gabf. In this example we have d(u) = a f bg with f = aabbab and g = aababb giving gabf = aababb.ab.aabbab = d(w').

The rewriting R(a f bg) = gabf is a function on Dyck words of same size n that may be described by a tree [T.sub.n] as in Figure 4 where edges (w, R(w)) are oriented downward. There is a loop not drawn at the root of the tree related to the single fixed point R([(ab).sup.n]) = [(ab).sup.n]. We define prerank p(w) of any Dyck word as its distance to the root [(ab).sup.n] or in other words p(w) = min{k\k > 0 and [R.sup.k](w) = [(ab).sup.n]}. This is motivated by a count of the iterations required in the loop of the algorithm.

3.3 Computing a parking configuration equivalent to u

Lemma 2 Two configurations u and v are toppling equivalent in [K.sub.n] if and only if the following holds:

deg(u) = deg(v) and for any 1 [less than or equal to] i, j [less than or equal to] n: [u.sub.i] - [u.sub.j] = [v.sub.i] - [v.sub.j] (mod n) (2)

Proof: It suffices to show that the configuration u is toppling equivalent to 0 if and only if deg(u) = 0 and [u.sub.i] - [u.sub.j] = 0(mod n). But this follows from the fact that these relations are not modified by any toppling and are satisfied by the parking configuration equivalent to 0 which is equal to (0, 0, ..., 0).

Given a configuration u one can find a configuration v toppling equivalent to u and such that 0 < [v.sub.i] < n for any 1 [less than or equal to] i [less than or equal to] n - 1 by setting [v.sub.1] = 0, then [v.sub.i] = [u.sub.i] - [u.sub.1] (mod n) and [v.sub.n] = deg(u) - [[summation].sup.n- 1.sub.i=1][v.sub.i]. From such a v one builds the parking configuration using the following:

Proposition 6 Let u be a configuration satisfying equation (1) and let w = D(u). The classical Cyclic Lemma states that there exists a unique conjugate w' of w which is equal to a Dyck word followed by a letter b. Consider the configuration v such that D(v) = w' and such that [v.sub.n] is such that deg(u) = deg(v), then v is the sorted version of the parking configuration equivalent to u.

4 Symmetry of area and prerank distribution on Dyck words

4.1 A symmetry and a bijective proof of it

The area of a Dyck word w is defined by area(w) = [[summation].sub.w'], h(w') where w' runs over all prefixes of w ending with the letter a. We also consider for a Dyck word w the largest prefix u of it among those whose height is H(w), and define the coheight [h.sup.c](w') for any prefix w' of w ending with an a, this coheight is H(w) - h(w') if w' is not larger than u and it is H(w) - h(w') - 1 if w' is larger that u. Using Proposition 5 it is possible to prove thatprerank(w) = [[summation].sub.w'], [h.sup.c](w') where w' runs over all prefixes of w ending with the letter a.

We consider the generating function on Dyck words of size n counted according to the statistics area and prerank:

[D.sup.area,prerank.sub.n](q, t) = [summation over w][q.sup.area(w)][t.sup.prerank(w)].

Theorem 3 For any n [greater than or equal to] 1,we have the symmetry [D.sup.area,prerank.sub.n] (q, t) = [D.sup.area,prerank.sub.n] (t, q).

The proof follows from an involution [PHI] on Dyck words that exchanges areas and preranks, and is defined as follows:

A non-empty Dyck word w admits a non-ambiguous last maximum decomposition w = ubv where u is the largest prefix of w among those whose height is H(w). The mirror image w of the word w whose letters are [w.sub.1][w.sub.2] ... [w.sub.k-1][w.sub.k] is the word [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; notice that we do not exchange letters a and b. The involution [PHI] is defined from the last maximum decomposition [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This symmetry can be refined at the level of occurrences of the letter a in a Dyck word.

Lemma 3 For any Dyck word w of size n there is a bijection from the occurrences of the letter a in w into those of the letter a in [PHI](w) that exchanges heights and coheights. This bijection associates to an occurrence of a in w its image by the involution [PHI].

The involution [PHI] has another property with respect to the dinv parameter introduced by Haiman (see Haglund (2008) for the definition of dinv).

Proposition 7 For any Dyck word w, dinv([PHI](w)) = dinv(w).

An immediate corollary is that the bistatistic (prerank, dinv) is the image by [phi] of the bistatistic (area, dinv) which defines the q, t-Catalan numbers studied by A. Garsia, M. Haiman, J. Haglund.

Our definition of [PHI] may be seen, using mirror image, in the classical cyclic lemma attributed to Dvoretsky and Motzkin (1947). A word w on the alphabet {a, b} is called a quasi-balanced word of size n if [[absolute value of w].sub.a] = n and [[absolute value of w].sub.b] = n + 1. The cyclic lemma states that for any quasi-balanced word w, among the 2n + 1 conjugates of the bi-infinite periodic word [w.sup.Z] exactly one may be written [(w'b).sup.Z] where w' is a Dyck word of size n. The image of this via the mirror mapping is related to our definition of [PHI]: among the 2n + 1 conjugates of [([??]).sup.Z] exactly one may be written [(w"b).sup.Z] where w" is a Dyck word and w" = [PHI](w').

It is also possible to prove that the involution [PHI] on Dyck paths satisfies a commutativity relation with the function [zeta] introduced in Haglund (2008) (page 50). More precisely: Flip.[zeta] = [zeta][PHI], where Flip is the map that reflects a Dyck word and exchanges occurrences of a's and b's (ii)

4.2 Another description of the rank algorithm

The conjugate [PHI]R[PHI] of function R with this bijection [PHI] is described by the following lemma which leads to another description of the rank algorithm.

Lemma 4 For any non-empty Dyck word w, let [PHI](w) = ubv = (u'a)bv be the last maximum decomposition of [PHI](w) then [PHI](R(w)) = u'bav.

The building of the tree in Fig. 4 becomes obvious from this viewpoint, when the nodes of [T.sub.n] are labeled by [PHI](w) instead of w since the rewriting described by the edge ([PHI](d), [PHI](R(d))) corresponds to a flip of the last highest peak ab into a valley ba.

4.3 Computing the area, prerank distribution

We currently have two ways to describe the distribution of the bistatistic (area, prerank) on Dyck words of given size n. First, we have a non-ambiguous shuffle of any possible distribution of pairs heights and coheights on occurences of letter a leading to all Dyck words with this distribution:

Proposition 8 For any n [greater than or equal to] 0 and k such that 1 [less than or equal to] k [less than or equal to] n, let c = ([c.sub.0], [c.sub.1], ... [c.sub.2k-2]) be a composition of n - k into 2k - 1 parts. The number [N.sub.n,k,c] of Dyck words such that 1 + [c.sub.2i] is the number of letters a of height i and coheight k - i and [c.sub.2i+1] is the number of letters a of height i and coheight k - 1 - i is




Using an interpretation of the decomposition at last maximum of the Dyck word in terms of heaps of dimers in the framework of Viennot's theory of heaps (see Krattenthaler (2006)) we also have:

Lemma 5 Let [([T.sub.n](y, z)).sub.n[greater than or equal to]0] the polynomials recursively defined by [T.sub.0](y, z) = 1 = [T.sub.1](y, z) and for n [greater than or equal to] 2,


5 On degree and rank distribution

5.1 On any graph G

Given a sink, labeled by n in our notation, the toppling classes of configurations may be indexed by G-parking configurations ([pi], s) where [pi] belongs to HG the finite set of restrictions of G-parking configurations outside the sink and s [member of] Z is a number of tokens on the sink. These indices are used to define the Laurent series related to the distribution of degree and rank by


Since a negative degree implies a rank equal to -1, using Proposition 4 for higher degrees we can consider that the relevant part of this series is a ("Laurent") polynomial [,rank.sub.G,[0,2m-2n]](x, r) defined on configurations with intermediate degree, that is belonging to the interval [0, 2m - 2n]. Hence we write:

[,rank.sub.G](x, r) = [(rx).sup.-1][absolute value of [[PI].sub.G]]/1 - [x.sup.-1] + [,rank.sub.G,[0,2m-2n]](x, r) + x[([x.sup.2]r).sup.m-n][absolute value of [[PI].sub.G]]/1 - xr.

Theorem 2 uses configuration [kappa] of degree 2m - 2n to give a relation between the rank and degree of two configurations u and [kappa] - u, it implies the following formula expressing symmetry of degree and rank distribution:

[,rank.sub.G](x, r) = [(r[x.sup.2]).sup.m-n][P.sup.egree,rank.sub.G] (1/xr, r).

The non-effective configurations are exactly those of rank -1 and the degree distribution on these configurations may be related to an evaluation of the Tutte polynomial [T.sub.G](x, y) of the graph G (see Lopez (1997)) where x (respectively y) counts internal (respectively external) activity:

[[r.sup.-1]][P.sup.egree,rank.sub.G](x, r) = 1/1 - [x.sup.-1] [T.sub.G](1, x).

5.2 On complete graphs

In the particular case the complete graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we define the distribution of degree and rank at the level of orbits under the action of Sn-1 leading to the " Laurent " polynomial:

[,rank.sub.n](x, r) = [summation over u] [][r.sup.rank(u)],

where u runs over sorted parking configurations such that degree(u) [member of] [0, n(n - 3)].

Baker and Norine s theorem is compatible with the action of [S.sub.n-1] so we also have the symmetry

[,rank.sub.n](x,r) = [(r[x.sup.2]).sup.n(n-3)/2] [,rank.sub.n](1/xr, r).

We conclude this extended abstract by the partial announcement of an enumerative result we obtained recently via combinatorial considerations on the analysis of our algorithm computing the rank. This can be stated as follows:


where [[z.sup.n]]f(z) denotes the coefficient of [z.sup.n] in power sum f(z), and F([q.sub.1], [q.sub.2]; z) is an explicit rational function in [q.sub.1] = [x.sup.-1], [q.sub.2] = xr, z, C([q.sub.1], z), C([q.sub.1], [q.sub.1]z), C([q.sub.2]; z) and C([q.sub.2]; [q.sub.2]z) where

C(q; z) = [summation over w dyck] [q.sup.area(w)] [z.sup.size(z)]

is the well known Carlitz q-analogue of Catalan numbers.


O. Amini and M. Manjunath. Riemann-Roch for sub-lattices of the root lattice An. Electronic J. of Combinatorics, 17:R124, 2010.

P. Bak, C. Tang, and K. Wiesenfeld. Self-organised criticality. Physical Review A., 38:364-374, 1988.

M. Baker and S. Norine. Riemann-Roch and Abel-Jacobi theory on a finite graph. Advances in Mathematics, 215:766-788, 2007.

N. Biggs. Chip-firing and the critical group of a graph. J. of Algebraic Combinatorics, 9:25-45, 1999.

A. Bjorner, L. Lovasz, and P.Shor. Chip-firing games on graphs. European J. Combin, 12:283-291, 1991.

R. Cori and D. Rossin. On the sandpile group of dual graphs. Europ. J. Comb, 21:447-459, 2000.

D. Dhar. Self-organized critical state of the sandpile automaton models. Phys. Rev. Lett., 64:1613-1616, 1990.

D. Dhar and S. Majumdar. Equivalence between the Abelian sandpile model and the q [right arrow] 0 limit of the Potts model. PhysicaA, 185:129-135, 1992.

A. Dvoretsky and T. Motzkin. A problem of arrangements. Duke Math. J., 14:305- 313, 1947.

H. M. Farkas and I. Kra. Riemann Surfaces. Graduate Texts in Mathematics, Springer, 1992.

A. Garsia and M. Haiman. A remarkable q, t-catalan sequence and q-lagrange inversion. J. Algebraic Combin., 5:191-244, 1996.

J. Haglund. The q, t-Catalan numbers and the space of diagonal harmonics. AMS University Lectures Series, 2008.

C. Krattenthaler. The theory of heaps and the Cartier-Foata monoid. available at:, 2006.

C. M. Lopez. Chip firing and Tutte polynomials. Ann. Combin., 3:253-259, 1997.

M. Manjunath. The rank of a divisor on a finite graph: geometry and computation. preprint, arXiv:1111.7251, 2011.

(i) We recall that configurations may have a negative number of tokens.

(ii) We thank one of the anonymous referees of FPSAC 2013 to have suggested the existence of this link

Robert Cori (1) and Yvan Le Borgne (12)

(1) LaBRI, 351 cours de la Liberation, F-33450 Talence, France

(2) CNRS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Cori, Robert; Le Borgne, Yvan
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUFR
Date:Jan 1, 2013
Previous Article:Generalized monotone triangles: an extended combinatorial reciprocity theorem.
Next Article:Operators of equivalent sorting power and related Wilf-equivalences.

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |