# Yamanouchi toppling--extended abstract.

1 Introduction

In [3] A. Bjorner, L. Lovasz and P. Schor have studied a solitary game called the chip-firing game which is closely related to the sandpile model of Dhar [6], arising in physics. In more recent papers some developments around this game were proposed. Musiker [11] introduced an unexpected relationship with elliptic curves, Norine and Baker [1] by means of an analogous game, proposed a Riemann-Roch formula for graphs, for which Cori and Le Borgne [5] presented a purely combinatorial description. An algebraic presentation of the theory can be found in [2] and [12]. In this paper we investigate this game, which we refer to as the toppling game, by exhibiting a wide range of connections with classical orthogonal polynomials and symmetric functions. We focus our attention on a noteworthy class of admissible moves, that we have called Yamanouchi moves. These moves are built up starting from suitable elementary moves, denoted by [T.sub.1], [T.sub.2], ..., [T.sub.n] and called topplings. A first crucial fact is that Yamanouchi moves are not invertible, this provides a partial order on the set of configurations and then principal order ideals may be considered. A second interesting point is that topplings can be seen as operators acting on the ring of formal series Z[[[x.sup.[+ or -]1.sub.1], [x.sup.[+ or -]1.sub.2], ..., [x.sup.[+ or -]1.sub.n]]], and in particular on the ring of polynomials Z[[x.sub.1], [x.sub.2], ..., [x.sub.n]]. Hence, each principal order ideal [H.sub.[alpha]] = [[beta] | [alpha] [[right arrow].sub.y] [beta]}, which stores all configurations obtained from a starting configuration a by means of a Yamanouchi move, may be identified with the series

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Topplings generate a group G, the toppling group, attached to any graph G. By setting [T.sub.[i]] = [T.sub.1][T.sub.2] ... [T.sub.i] we obtain algebraically independent elements spanning a subalgebra Z[[G].sub.[greater than or equal to]] of the group algebra Z[G]. We show there exists an operator [tau], with [[tau].sup.-1] [member of] Z[[G].sub.[greater than or equal to]], which depends on G but not on [alpha], such that [tau] x [x.sup.[alpha]] = [H.sub.[alpha]](x) and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By setting [T.sub.[i,j]] = [T.sub.[i]][T.sub.[i+1]] ... [T.sup.[j-1]] we obtain a further set of generators of Z[[G].sub.[greater than or equal to]] yielding a deformation of [tau] and a weighted version of [H.sub.[alpha]](x). More precisely, we recover

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and also we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where C([lambda]) counts the number of pairwise distinct decompositions in terms of the generators [T.sub.[i,j]] of the unique element [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the toppling group G such that [beta] = [T.sup.[lambda]]([alpha]). Parameters [z.sub.1], [z.sub.2], [z.sub.3], q may be introduced in order to keep track of certain statistics [l.sub.1], [l.sub.2], [l.sub.3], d defined on the set of all decompositions of a given TA. Then, the following series can be considered,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Such a series satisfies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since [??][([z.sub.1], [z.sub.2], [z.sub.3], q).sup.-1] = [??]([z.sub.1], [z.sub.2], (1 - q)[z.sub.3], q[(q - 1).sup.- 1]), then a combinatorial description of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is obtained for free. Moreover, [l.sub.1] [greater than or equal to] [l.sub.2] [greater than or equal to] [l.sub.3] [greater than or equal to] d [greater than or equal to] 0 implies that the coefficient of [x.sup.[beta]] in [[??].sub.[alpha]](x; [z.sub.1], [z.sub.2], [z.sub.3], q), as well as that in [[??].sub.[alpha]](x; [z.sub.1], [z.sub.2], [z.sub.3], q), is a polynomial with integer coefficients. Then, one can consider a projection [PI] such that [PI][x.sup.[beta]] = [x.sup.[beta]] if [beta] [member of] [N.sup.n], and [PI][x.sup.[beta]] = 0 otherwise. Hence both [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], with a ranging over [N.sup.n], are bases of Z[[z.sub.1], [z.sub.2], [z.sub.3], q][x]. Our interest in the toppling game is explained by focusing the attention on a very special family of graphs [{[L.sub.n]}.sub.n[greater than or equal to]1]. In this case, we prove that the polynomial sequence [{[PI][[??].sub.[alpha]](x; [z.sub.1], [z.sub.2], [z.sub.3], q)}.sub.[alpha]], via a suitable linear functional of umbral type [14], yields to a parametrized extension of classical orthogonal polynomials. More concretely, set [alpha] = (n - 1, n - 1, ..., n - 1) and let X = [X.sub.1], [X.sub.2], ..., [X.sub.n-1] denote i.i.d. random variables. Then, denote by [p.sub.n-1]([z.sub.1], [z.sub.2], [z.sub.2], q; t) the expected value of the polynomial obtained by replacing [x.sub.1] = t and [x.sub.i+1] = [X.sub.i] in [[??].sub.a](x; [z.sub.1], [z.sub.2], [z.sub.3], q):

[p.sub.n-1](t; [z.sub.1], [z.sub.2], [z.sub.3], q) = E[[??].sub.[alpha]](t, [X.sub.1], ..., [X.sub.n-1]; [z.sub.1], [z.sub.2], [z.sub.3], q).

The polynomial sequence {[p.sub.n](t; [z.sub.1], [z.sub.2], [z.sub.3], q)}n generalizes the orthogonal polynomial system associated with X [4, 13]. Classical cases, like Hermite, Laguerre, Poisson-Charlier, Chebyshev arise for [z.sub.1] = [z.sub.2] = [z.sub.3] = q = 1 when suitable random variables are chosen. Moreover, if we replace [x.sup.[beta]] with complete homogeneous symmetric functions [h.sub.[beta]](x) then an action of the toppling group on symmetric functions is obtained. In this context, when G = [L.sub.n] the action of the [T.sub.[i,j]]'s turns out to be closely related to that of raising operators [8] and this leads to a generalization of Hall-Littlewood symmetric functions [9] [{[R.sub.[lambda]](x; t)}.sub.[lambda]]. The toppling game not only provides a new elementary combinatorial basis for symmetric functions and orthogonal polynomials [10], but it also suggests further generalizations to analogous environments defined starting from further families of graphs [{[G.sub.n]}.sub.n].

2 The toppling game

Here and in the following, by a graph G = (V, E) we will mean a connected graph, with set of vertices V = {[[upsilon].sub.1], [[upsilon].sub.2], ..., [[upsilon].sub.n]}, and whose set of undirected edges E contains at most one edge {[[upsilon].sub.i], [[upsilon].sub.j]} for each pair ([[upsilon].sub.i], [[upsilon].sub.j]). Also, we say that [[upsilon].sub.i] and [[upsilon].sub.j] are neighbours whenever {[[upsilon].sub.i], [[upsilon].sub.j]} [member of] E. A configuration on G is a map, [alpha]: [[upsilon].sub.i] [member of] V [??] [alpha]([[upsilon].sub.i]) [member of] Z, associating each vertex [[upsilon].sub.i] with an integral weight [alpha]([[upsilon].sub.i]). If we set [[alpha].sub.i] = [alpha]([[upsilon].sub.i]) then we may identify any configuration a with the array ([[alpha].sup.1], [[alpha].sub.2], ..., [[alpha].sub.n]). We set [[epsilon].sub.i] = ([[delta].sub.i1], [[delta].sub.i2], ..., [[delta].sub.in]) so that [[epsilon].sub.i] is the configuration associating vi with 1 and [[upsilon].sub.j] with 0 if j [not equal to] i. A toppling of the vertex [[upsilon].sub.i] is a map [T.sup.G.sub.i]: [Z.sup.n] [right arrow] [Z.sup.n] defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

and [d.sub.i] = [absolute value of {[[upsilon].sub.j] | {[[upsilon].sub.i], [[upsilon].sub.j]} [member of] E}] is the degree of [[upsilon].sub.i]. Roughly speaking, the map [T.sup.G.sub.i] increases by 1 the weight [[alpha].sub.j] of each neighbour [[upsilon].sub.j] of [[upsilon].sub.i], and simultaneously decreases by [d.sub.i] the weight [a.sub.i]. As a trivial consequence we deduce that the size [absolute value of [alpha]] = [[alpha].sub.1] + [[alpha].sub.2] + ... + [[alpha].sub.n] of any [alpha] [member of] [Z.sup.n] is preserved by each toppling [T.sup.G.sub.i]. One may visualize topplings as special moves of a suitable combinatorial game defined on the graph G. More precisely, fix a starting configuration [alpha] = ([[alpha].sub.1], [[alpha].sub.2], ..., [[alpha].sub.n]) on the graph and label each vertex [[upsilon].sub.i] with its own weight [[alpha].sub.i]. By "firing" the vertex [[upsilon].sub.i] we change the configuration [alpha] into a new configuration [beta] = [T.sup.G.sub.i]([alpha]). A move of the toppling game simply is a finite sequence of fired vertices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], possibly not all distinct. Now, let us fix two configurations [alpha] and on a graph G and let us look for all possible moves changing [alpha] into [beta]. Also, assume that certain moves are forbidden in the game, so that each player is forced to perform only those moves that are in a given set M of admissible moves. Henceforth, by writing [alpha] [[right arrow].sub.M] [beta] we will mean that a can be changed into ft by means of a suitable admissible move in M. When useful, M will be identified with the corresponding set of monomials belonging to the free monoid [T.sup.*] generated by the alphabet T = {[T.sup.G.sub.1], [T.sup.G.sub.2], ..., [T.sup.G.sub.n]}. At this point a possible strategy of a player passes through the determination of those moves of minimal length (i.e. minimal number of fired vertices) that are admissible and that change [alpha] into [beta]. Therefore, the toppling game starts once a pair (G, M) is chosen, and two configurations [alpha], [beta] [member of] [Z.sup.n] are given so that [alpha] [[right arrow].sub.M] [beta]. Hence, the idea is to characterize, in an explicit way, the subset [M.sub.[alpha],[beta]] of all admissible moves changing a into ft, then to determine all moves in [M.sub.[alpha],[beta]] of minimal length. In the following we will focus our attention on a special set of admissible moves, which we name Yamanouchi moves, defined by Y = {[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is Yamanouchi}. Recall that a sequence, or word, w = [i.sub.1][i.sub.2] ... [i.sub.l] of positive integers is said to be Yamanouchi if and only if, for all k and for all i, the number occ(i, k), of occurrences of i in [i.sub.1][i.sub.2] ... [i.sub.k], satisfies occ(i, k) [greater than or equal to] occ(i + 1, k). If w = [i.sub.1][i.sub.2] ... [i.sub.l] then we set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and write [alpha] [[right arrow].sub.w] [beta] if and only if [beta] = [T.sup.G.sub.w]([alpha]). Associated with each Yamanouchi word w = [i.sub.1][i.sub.2] ... [i.sub.l] there is an integer partition [lambda](w) = ([[lambda].sub.1], [[lambda].sub.2], ...) whose ith part [[lambda].sub.i] equals the number occ(i, l) of occurrences of i in w. A suitable filling of the Young diagram of [lambda](w) yields a coding of w in terms of a standard Young tableau. More precisely, the Young tableau associated with w is the unique tableaux of shape [lambda](w) whose ith row (of length [[lambda].sub.i]) stores all j such that [w.sub.j] = i. This fixes a bijection between the set of all Yamanouchi words of l letters and the set of all standard Young tableaux of l boxes.

Proposition 1 If [alpha] [[right arrow].sub.w] [beta] and [lambda] = [lambda](w) then for all w' such that [lambda] = [lambda](w') we have [alpha] [[right arrow].sub.w'] [beta]. If [alpha] [[right arrow].sub.w] [beta] then the set of all Yamanouchi words extracted from all standard Young tableaux of shape [lambda](w) corresponds to moves in [[gamma].sub.[alpha],[beta]]. On the other hand the converse is not true. Hence, in order to get an explicit characterization of [[gamma].sub.[alpha],[beta]] and of those moves in yo,p of minimal length we need a slightly deeper investigation.

3 The toppling group

Assume a graph G = (V, E) is given and write [T.sub.1], [T.sub.2], ..., [T.sub.n] instead of [T.sup.G.sub.1], [T.sup.G.sub.2], ..., [T.sup.G.sub.n.] The toppling group associated with G is the group G generated by [T.sub.1], [T.sub.2], ..., [T.sub.n]. Let 1 denote its unity. By virtue of (1) we have [T.sub.i][T.sub.j] = [T.sub.j][T.sub.i] for all i, j, and then G is commutative. In particular, this says that all g [member of] G may be expressed in terms of topplings as a product of type [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for a suitable array of integers a = ([a.sub.1], [a.sub.2], ..., [a.sub.n]) [member of] [Z.sup.n]. On the other hand, it is also easy to verify that [T.sub.1][T.sub.2] ... [T.sub.n]([alpha]) = [alpha] for all [alpha], and then we have [T.sub.1][T.sub.2] ... [T.sub.n] = 1. As a consequence, all g [member of] G admit a presentation [T.sup.a] with a [member of] [N.sup.n]. In fact, if g = [T.sup.a] and if a [not member of] [N.sup.n] then let k = min{[a.sub.1], [a.sub.2], ..., [a.sub.n]} and set b = a - k([e.sub.1] + [e.sub.2] + ... + [e.sub.n]). Then b [member of] [N.sup.n] and [T.sup.b] = [T.sup.a][([T.sub.1][T.sub.2] ... [T.sub.n]).sup.k] = [T.sup.a] = g. The following lemma characterizes all presentations of the unity 1 in G.

Lemma 2 For all graphs G we have [T.sup.a] = 1 if and only if a = k([[epsilon].sub.1] + [[epsilon].sub.2] + ... + [[epsilon].sub.n]).

A first consequence of Lemma 2 is that apart from [T.sub.i][T.sub.j] = [T.sub.j][T.sub.i] and [T.sub.1][T.sub.2] ... [T.sub.n] = 1 there are not further relations satisfied by [T.sub.1], [T.sub.2], ..., [T.sub.n]. This provides a characterization of all distinct presentations of any element in the toppling group G.

Theorem 3 For all graphs G and for all a, b [member of] [N.sup.n] we have [T.sup.a] = [T.sup.b] if and only if there exists k [member of] Z such that b = a + k([[epsilon].sub.1] + [[epsilon].sub.2] + ... + [[epsilon].sub.n]).

Now, once a [member of] [N.sup.n] is chosen, we may set k = min{[a.sub.1], [a.sub.2], ..., [a.sub.n]} and define b = a- -k([[epsilon].sub.1] + [[epsilon].sub.2] + ... + [[epsilon].sub.n]). Clearly [T.sup.a] = [T.sup.b] and b is the unique array in Nn of minimal size with this property. In other terms, [T.sup.b] is the unique reduced decomposition of g = [T.sup.a].

Theorem 4 Let (G, Y) be a toppling game. If [alpha] [[right arrow].sub.y] [beta] then there exists a unique partition [lambda] = ([[lambda].sub.1], [[lambda].sub.2], ..., [[lambda].sub.l]) with l [less than or equal to] n - 1 parts such that [T.sup.[lambda]]([alpha]) = [beta]. Hence, [[gamma].sub.[alpha],[beta]] consists of exactly all Yamanuochi moves associated with standard Young tableaux of shape [mu] = [lambda] + k([[epsilon].sub.1] + [[epsilon].sub.1] + ... + [[epsilon].sub.n]), for a suitable k [member of] N. In particular, all minimal moves in [[gamma].sub.[alpha],[beta]] are the Yamanuochi moves associated with standard Young tableaux of shape [lambda].

4 A partial order on [Z.sup.n]

Our next goal is the following: we want to characterize in an explicit way the sets [H.sub.[alpha]] = {[beta] [member of] [Z.sup.n] | [alpha] [[right arrow].sub.y] [beta]} defined for all [alpha] [member of] [Z.sup.n]. To this aim, we denote by [I.sub.n] the set of all a = ([a.sub.1], [a.sub.2], ..., [a.sub.n]) [member of] [N.sup.n] such that [a.sub.i] = 0 for some i. Note that, for all g [member of] G there is exactly one a [member of] [I.sub.n] such that g = [T.sup.a]. In particular, [T.sup.a] is the reduced decomposition of g. This gives the following characterization of the group algebra Z[G].

Theorem 5 We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and in particular

Z[G] [congruent to] Z[[x.sub.1], [x.sub.2], ..., [x.sub.n]]/<1 - [x.sub.1][x.sub.2] ... [x.sub.n]>,

with <1 - [x.sub.1][x.sub.2] ... [x.sub.n]> denoting the principal ideal generated by 1 - [x.sub.1][x.sub.2] ... [x.sub.n].

We consider not only elements in Z[G] but we also admit formal series in [T.sub.1], [T.sub.2], ..., [T.sub.n]. In particular we set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If we associate each [alpha] [member of] [Z.sup.n] with a monomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] then we may translate the action of G on [Z.sup.n] into an action of Z[[G]], and in particular of Z[G], on the ring of formal series

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This is done by setting [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all a [member of] [N.sup.n] and for all a [member of] [Z.sup.n]. Clearly, knowing the set [H.sub.[alpha]] = {[beta] [member of] [Z.sup.n] | [alpha] [[right arrow].sub.y] [beta]} is equivalent to knowing the formal series

[H.sub.[alpha]](x) = [summation over ([alpha][right arrow][gamma][beta])][x.sup.[beta]].

In the following we will determine a special element [tau] [member of] Z[[G]] satisfying [tau] x [x.sup.[alpha]] = [H.sub.[alpha]](x). Before doing that we introduce a new relation [[less than or equal to].sub.G] on [Z.sup.n]: set [beta] [[less than or equal to].sub.G] [alpha] if and only if [beta] = [T.sup.[lambda]](a) with [[lambda].sub.1] [greater than or equal to] [[lambda].sub.2] [greater than or equal to] ... [greater than or equal to] [[lambda].sub.n] [greater than or equal to] 0. Clearly, if [[lambda].sub.n] = 0 then we may define [mu] = [lambda] - [[lambda].sub.n]([[epsilon].sub.1] + [[epsilon].sub.2] + ... + [[epsilon].sub.n]) so that [T.sup.[lambda]](a) = [T.sup.[lambda]]([beta]) and [T.sup.[mu]] is a reduced decomposition for [T.sup.[lambda]]. Note that [mu] is an integer partition with at most n - 1 parts. Henceforth we will denote by [P.sub.n] the set of all integer partitions with at most n - 1 parts or, equivalently the subset of all [lambda]'s in [I.sub.n] such that [[lambda].sub.1] [greater than or equal to] [[lambda].sub.2] [greater than or equal to] ... [greater than or equal to] [[lambda].sub.n]. The following proposition makes explicit the relation between the relation [[less than or equal to].sub.G] and the toppling game.

Proposition 6 For all graphs G the relation [[less than or equal to].sub.G] is a partial order on [Z.sup.n]. Moreover, [[less than or equal to].sub.G] and [right arrow][gamma] agree on Zn.

Proposition 6 assures us that the set [H.sub.[alpha]] is nothing but the order ideal generated by [alpha], that is [H.sub.[alpha]] = {[beta] | [beta] [[less than or equal to].sub.G] [alpha]}. Let us consider the following element in Z[[G]]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and let it act on the monomial [x.sup.[alpha]]. Being [beta] = [T.sup.[lambda]]([alpha]) for at most one [lambda] [member of] [P.sub.n], then we recover

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The crucial point is that a closed expression of [tau] is available by introducing suitable elements of G. More precisely, we define

[T.sub.[i]] = [T.sub.1][T.sub.2] ... [T.sub.i] for all i = 1, 2, ..., n - 1.

Note that [T.sub.[i]] may be thought of as a Yamanouchi move associated with a Young standard tableau of one column filled with 1, 2, ..., i.

Theorem 7 Let [lambda] [member of] [P.sub.n] and denote by [lambda]' = ([[lambda]'.sub.1], [[lambda]'.sub.2], ..., [[lambda]'.sub.l]) the conjugate of A. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Corollary 8 We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now, we may write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Moreover, straightforward computations will prove the following theorem.

Theorem 9 For each graph G there exists a formal series t(x) [member of] Z [[[x.sup.[+ or -]1.sub.1], [x.sup.[+ or - ]1.sub.2], ..., [x.sup.[+ or -]1.sub.n]] such that [H.sub.[alpha]](x) = [tau](x)[x.sup.[alpha]], for all [alpha] [member of] [Z.sup.n].

5 A special set of Yamanouchi moves

If G is the toppling group associated with a graph G then we set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Clearly Z[[G].sub.[greater than or equal to]] is a subalgebra of Z[G] and Theorem 7 assures us it is exactly the subalgebra generated by [T.sub.[1]], [T.sub.[2]], ..., [T.sub.[n-1]]. Let us consider a wider set of generators of Z[G[].sub.[greater than or equal to]] defined by [T.sub.[i,j]] = [T.sub.[i]][T.sub.[i+1]] ... [T.sub.[j-1]] for all 1 [less than or equal to] i < j [less than or equal to] n. Note that each [T.sub.[i,j]] is a Yamanouchi move associated with a tableau whose shape consists of consecutive integers. Obviously [T.sub.[i]] = [T.sub.[i,i+1]] so that the [T.sub.[i,j]]'s generate the whole Z[[G].sub.[greater than or equal to]]. On the other hand, the presentation of any g [member of] G as a product of these generators is in general not unique. In order to find a reduced decomposition of g = [T.sup.[lambda]], that is a presentation that involves a minimal number of generators, we write [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then rearrange and associate so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and each product ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) consists of an increasing sequence of consecutive integers. Thus, a reduced decomposition of TA is given by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Example 1 If [lambda] = (8, 7, 4, 3, 2, 2, 1) then [lambda]' = (7, 6, 4, 3, 2, 2, 2, 1). We recover

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A reduced decomposition of [T.sup.[lambda]] is given [T.sub.[1,5]][T.sup.2.sub.[2,3]][T.sub.[6,8]].

A decomposition [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is said to be square free if and only if each generator occurs at most once. For instance, [T.sub.[1,2]][T.sub.[1,3]][T.sub.[2,5]] is square free but [T.sub.[1,2]][T.sub.[1,2]][T.sub.[2,3]][T.sub.[2,5]] is not square free. Also, note that [T.sub.[1,2]][T.sub.[1,3]][T.sub.[2,5]] = [T.sub.[1,2]][T.sub.[1,2]][T.sub.[2,3]][T.sub.[2,5]] so that a given element in Z[[G].sub.[greater than or equal to]] may have both square free and not square free decompositions. Now, consider the operator [??] in Z[[G]] defined by

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

Note that [??] is the analogue of [tau] for the generators [T.sub.[i,j]]'s. Moreover, we recover

with C([lambda]) being the number of pairwise distinct presentations of g = [T.sup.[lambda]] in terms of the generators [T.sub.[i,j]]'s. Finally, we may write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

with [lambda] denoting the unique element in [P.sub.n] such that [beta] = [T.sup.[lambda]]([alpha]).

6 The graph Ln and classical orthogonal polynomials

In this section we restrict our attention to a special family of graphs, denoted by [{[L.sub.n]}.sub.n], and defined by [L.sub.n] = ([V.sub.n], [E.sub.n]), with [V.sub.n] = {[[upsilon].sub.1], [[upsilon].sub.2], ..., [[upsilon].sub.n]} and [E.sub.n] = {{[[upsilon].sub.1], [[upsilon].sub.2]}, {[[upsilon].sub.2], [[upsilon].sub.3]}, ..., {[[upsilon].sub.n-1], [[upsilon].sub.n]}}, for all n [greater than or equal to] 1. Now, assume a linear functional L: C[t] [right arrow] C is given. An orthogonal polynomial system associated with L is a polynomial sequence [{[p.sub.n](t)}.sub.n], with deg [p.sub.n] = n for all n [member of] N, such that [Lp.sub.n](t)[p.sub.m](t) = 0 if and only if n [not equal to] m. We refer to [4] for a background on this subject. The toppling game performed on the [L.sub.n]'s gives rise to a nice combinatorial framework for orthogonal polynomial systems. Consider the unique [p.sub.[alpha]](x) such that [x.sup.[alpha]] = [??] x [p.sub.[alpha]](x), or equivalently

[p.sub.[alpha]](x) = [[??].sup.-1] x [x.sub.[alpha]]. (3)

Observe that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where the sum is taken over all square free decompositions in G. Because the size of a configuration is preserved by the toppling game, [p.sub.[alpha]](x) is a homogeneous polynomial of degree [absolute value of [alpha]]. Moreover, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

so that [beta] ranges over all configurations that can be obtained from [alpha] by means of a square free Yamanouchi move [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Also, the coefficient [p.sub.[alpha],[beta]] of [x.sup.[beta]] in [p.sub.a[alpha](x) has the following combinatorial description,

[p.sub.[alpha],[beta]] = E[(-1).sup.l], (4)

where l ranges over all lengths of all square free Yamanouchi moves changing a into [beta]. In order to manipulate polynomials with an arbitrary large number of variables at the same time we set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now, let E: C[[x.sub.1], [x.sub.2], ...] [right arrow] C denote a map such that

1. for all n [greater than or equal to] 1 the restriction E: C[[x.sub.1], [x.sub.2], ..., [x.sub.n]] [right arrow] C is a linear functional;

2. for all n [greater than or equal to] 1, for all p [member of] C[[x.sub.1], [x.sub.2], ..., [x.sub.n]] and for all [sigma] [member of] [G.sub.n], we have Ep([x.sub.[sigma](1)], [x.sub.[sigma](2)], ..., [x.sub.[sigma](n)]) = Ep([x.sub.1], [x.sub.2], ..., [x.sub.n]).

Henceforth, we will call any functional of this type a symmetric functional. Once a symmetric functional E is given then we may define conditional operators [E.sub.i]: C[[x.sub.1], [x.sub.2], ...] [right arrow] C[[x.sub.i]] for all i [greater than or equal to] 1. Each [E.sub.i] is defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all [alpha] [member of] [N.sup.n]. Roughly speaking, each [E.sub.i] acts on C[[x.sub.1], ..., [x.sub.i-1], [x.sub.i+1], ...] as E acts, and fixes each polynomial in C[[x.sub.i]].

Remark 1 If [X.sub.1], [X.sub.2], ... is an infinite sequence of i.i.d. random variables, and if E is the expectation functional, then E: C[[X.sub.1], [X.sub.2], ...] [right arrow] C gives an example of symmetric functional.

Set G = [L.sub.n] and choose [alpha] [member of] [Z.sup.n]. In this case it is not too difficult to see that [T.sub.[i]] x [x.sup.[alpha]] = [x.sup.[alpha]][x.sub.i+1][x.sup.-1.sub.i] for all i = 1, 2, ..., n - 1. Hence, by means of straightforward computations we recover

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If [p.sub.n](x) is defined as in (3) with [alpha] = (n - 1, n - 1, ..., n - 1), then we recover

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, if [E.sub.1]: C[[x.sub.1], [x.sub.2], ...] [right arrow] C[[x.sub.1]] is a conditional operator associated with a symmetric functional E: C[[x.sub.1], [x.sub.2], ...] [right arrow] C, then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

with [e.sub.i]([x.sub.2], [x.sub.3], ..., [x.sub.n]) denoting the ith elementary symmetric polynomial in [x.sub.2], [x.sub.3], ..., [x.sub.n]. This implies that [p.sub.n-1]([x.sub.1]) is a polynomial in [x.sub.1] of degree at most n - 1. In particular, we have deg [p.sub.n] = n - 1 if and only if

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

On the other hand, since E is symmetric then we may replace each [x.sub.i] with [x.sub.i-1] in (5) without changing its value. Then we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This last condition, if satisfied for all n, will assures deg [p.sub.n] = n.

Theorem 10 (Orthogonal polynomial systems) Let E: C[[x.sub.1], [x.sub.2], ...] [right arrow] C be a symmetric functional, set G = [L.sub.n], and assume

E[[??].sup.-1] x [([x.sub.1][x.sub.2] ... [x.sub.n-1]).sup.n] [not equal to] 0 for all n [greater than or equal to] 1.

Then, the polynomial sequence [{[p.sub.n](t)}.sub.n] defined by

[p.sub.n-1]([x.sub.1]) = [E.sub.1][??] x [([x.sub.1][x.sub.2] ... [x.sub.n]).sup.n-1] [not equal to] 0 for all n [greater than or equal to] 1, satisfies [Ep.sub.n]([x.sub.1])[p.sub.m]([x.sub.1]) = 0 if and only n = m.

Theorem 10 gives us a general method to construct all orthogonal systems associated with a given linear functional L, provided they exist. In fact, given L: C[t] [right arrow] C, we consider the unique symmetric functional E: C[[x.sub.1], [x.sub.2], ...] [right arrow] C such that [Ex.sup.k.sub.i] = [Lt.sup.k], for all i [greater than or equal to] 1 and for all k [greater than or equal to] 0. Also, we set [a.sub.[alpha]] = [Ex.sup.[alpha]] for all [alpha] [member of] [Z.sup.n]. Hence, an orthogonal polynomial system [{[p.sub.n](t)}.sub.n] associated with L exists if and only if [E[??].sup.-1] [([x.sub.1][x.sub.2] ... [x.sub.n-1]).sup.n] [not equal to] 0 for all n [greater than or equal to] 1. Moreover, it is obtained by setting [p.sub.n-1]([x.sub.1]) = [E.sub.1][[??].sup.-1][([x.sub.1][x.sub.2] ... [x.sub.n]).sup.n-1]. So, the following combinatorial formula for [p.sub.n-1](t) is provided:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [alpha] = (n - 1, n - 1, ..., n - 1), [beta] ranges over all configurations that can be obtained from a by means of square free Yamanouchi move, and [p.sub.[alpha],[beta]] is the coefficient (4).

7 Statistics on the toppling group

In this section we focus our attention on the distribution of certain statistics [l.sub.1], [l.sub.2], [l.sub.3], d defined on the decompositions of elements in the toppling group in terms of the three families of generators {[T.sub.i] | i = 1, 2, ..., n}, {[T.sub.[i]] | i = 1, 2, ..., n - 1} and {[T.sub.[i,j]] | 1 [less than or equal to] i < j [less than or equal to] n}. More precisely, each [T.sup.[lambda]] [member of] G, [lambda] [member of] [P.sub.n], admits a unique expression, up to order of the [T.sub.i]'s, of type g = [T.sup.[lambda]]. This expression involves [l.sub.1] generators, and in particular [l.sub.1] equals the size of the partition [lambda]. Analogously, [T.sup.[lambda]] can be written in a unique way, up to order, in terms of the [T.sub.[i]]'s. In particular, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and this involves [l.sub.2] = [[lambda].sub.1] generators. On the other hand, there are C([lambda]) ways of writing [T.sup.[lambda]] as a product of generators [T.sub.[i,j]]'s. Each of such expressions involves a certain number, say [l.sub.3], of generators. Among these d [less than or equal to] [l.sub.3] are pairwise distinct.

Theorem 11 Set

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

Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where the sum ranges over all pairwise distinct decompositions [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We may define a parametrized version of the series [[??].sub.[alpha]](x) by setting

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

We recover

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where the coefficient of [x.sup.[beta]] stores the value of [l.sub.1], [l.sub.2], [l.sub.3], d relative to all pairwise distinct decompositions of the unique [T.sup.[lambda]] such that [beta] = [T.sup.[lambda]]([alpha]). As a consequence we obtain a parameterized extension of orthogonal polynomials. In fact, for all n [greater than or equal to] 1 and for all [alpha] [member of] [Z.sup.n] set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since [??][([z.sub.1], [z.sub.2], [z.sub.3], q).sup.-1] = [??]([z.sub.1], [z.sub.2], (1 - q)[z.sub.3], q[(q - 1).sup.- 1]) then the following combinatorial description is obtained:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since [l.sub.1] [less than or equal to] [l.sub.2] [greater than or equal to] [l.sub.3] [greater than or equal to] d [greater than or equal to] 0 then the coefficient of [x.sup.[beta]] in [[??].sub.[alpha]](x; [z.sub.1], [z.sub.2], [z.sub.3], q) is a polynomial with integer coefficients. By setting [z.sub.1] = [z.sub.2] = [z.sub.3] = q = 1 we have a non-zero contribution only for decompositions such that [l.sub.3] - d = 0, that is square free decompositions. At this point, one can consider a projection [PI] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and then both [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], with [alpha] ranging over [N.sup.n], are bases of Z[[z.sub.1], [z.sub.2], [z.sub.3], q][x]. By defining a suitable symmetric functional E, and by setting [p.sub.n- 1]([x.sub.1]; [z.sub.1], [z.sub.2], [z.sub.3], q) = [E.sub.1][??][([z.sub.1], [z.sub.2], [z.sub.3], q).sup.-1] x [([x.sub.1][x.sub.2] ... [x.sub.n]).sup.n-1] we obtain a polynomial sequence [{[p.sub.n](t; [z.sub.1], [z.sub.2], [z.sub.3], q)}.sub.n] that generalizes classical orthogonal polynomials.

Example 2 Hermite polynomials [{[H.sub.n](t)}.sub.n] forms an orthogonal polynomial system with respect to the linear functional L defined by [Lt.sup.k] = [EX.sup.k], where X is a Gaussian random variable. Assume X = [X.sub.1], [X.sub.2], ... are independent Gaussian random variables and set [x.sub.1] = t and [x.sub.i] = [X.sub.i-1]. Then the polynomial sequence {[p.sub.n](t; [z.sub.1], [z.sub.2], [z.sub.3], q)}n defined by

[p.sub.n-1](t; [z.sub.1], [z.sub.2], [z.sub.3], q) = E[PI][[??].sub.[alpha]](t, [X.sub.1], [X.sub.2], ..., [X.sub.n-1]; [z.sub.1], [z.sub.2], (1 - q)[z.sub.3], q/q - 1),

with [alpha] = (n - 1 , n - 1, ..., n - 1) generalizes Hermite polynomials.

8 New combinatorics for H-L symmetric polynomials

The toppling group G acts on the ring [LAMBDA](x; [z.sub.1], [z.sub.2], [z.sub.3], q), of symmetric polynomials in [x.sub.1], [x.sub.2], ..., [x.sub.n] with coefficients in Z[[z.sub.1], [z.sub.2], [z.sub.3], q]. In fact, let [h.sub.i](x) denote the ith complete homogeneous symmetric polynomial, and for all [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By assuming [h.sub.i](x) = 0 for i < 0 and [h.sub.0](x) = 1, we set

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

Finally, if [alpha] is a partition and if [s.sub.[alpha]](x) is a Schur polynomial then the symmetric polynomials [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] may be considered.

Theorem 12 For any graph G the sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], with a raging over all integer partitions, are bases of the ring [LAMBDA](x; [z.sub.1], [z.sub.2], [z.sub.3], q).

Again, the special case G = [L.sub.n] leads to some interesting consequences. In fact, we recover [T.sub.[i,j]] x [h.sub.[alpha]](x) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], so that [T.sub.[i,j]] acts as a "lowering operator" [R.sub.ji] (see [9], p.214). In particular this implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now, recall that the Hall-Littlewood symmetric polynomial [R.sub.[alpha]](x; t), [alpha] being a partition, satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Remark 2 Hence, [[??].sub.a](x; [z.sub.1], [z.sub.2], [z.sub.3], q) extends to four parameters Hall-Littlewood symmetric polynomials, and then several classical bases of symmetric functions such as Schur functions (t = 0). From this point of view they share some analogy with Macdonald symmetric polynomials. Moreover, the toppling game also yields several families of symmetric functions, each one attached to a graph G and then a general theory extending the classical case (G = [L.sub.n]) could be carried out.

Remark 3 Lowering operators [R.sub.ji]'s have a counterpart [R.sub.ij]'s called "raising operators"[8, 9]. In our setting they will arise as generators, say the [T.sub.[j,i]]'s, of the subalgebra Z[[G].sub.[less than or equal to]] spanned over Z by all [T.sup.[lambda]], with 0 [less than or equal to] [[lambda].sub.1] [less than or equal to] [[lambda].sub.2] ... [less than or equal to] [[lambda].sub.n].

References

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

[2] N. Biggs Chip-firing and the critical group of a graph J. of Algebraic Comb. 9, 25-45 (1999).

[3] A. Bjorner, L. Lovasz, P. Schor, Chip-firing game on graphs. Europ. J.of Comb. 12, 283-291 (1991).

[4] T.S. Chiahara, An introduction to Orthogonal polynomials. Mathematics and its applications - A series of monographs and texts 13, (1978).

[5] R. Cori, Y. Le Borgne, The Riemann-Roch theorem for graphs and the rank in complete graphs. Preprint, pp. 35 (2013).

[6] D. Dhar, Self-organized critical state of the sandpile automaton models. Phys. Rev. Lett., 64, 1613-1616 (1990.)

[7] D. Dhar, P. Ruelle, S. Sen, and D. Verma. Algebraic aspects of abelian sandpile model. J. Phys. A A28, 805-831 (1995).

[8] A. Garsia, Orthogonality of Milne's polynomials and raising operators. Discrete Mathematics 99, 247-264 (1992).

[9] I.G. Macdonald, Symmetric functions and Hall polynomials. Oxford Mathematical Monograph. Oxford University Press (1995).

[10] I.G. Macdonald, Affine Hecke algebras and orthogonal polynomials. Cambridge Tracts in Mathematics 157, Cambridge University Press (2003).

[11] G. Musiker, The critical groups of a family of graphs and elliptic curves over finite fields. Journal of Algebraic Combinatorics 30, 255-276 (2009).

[12] D. Perkinson, J. Perlman, and J. Wilmes. Primer for the algebraic geometry of sandpiles. preprint, arXiv:1112.6163, (2011).

[13] P. Petrullo, D. Senato, R. Simone, Orthogonal polynomials through the invarinat theory of binary forms. Preprint (2014).

[14] G.-C. Rota and B. Taylor, The classical umbral calculus. SIAM Journal of Mathematical Analysis 25(2), 694-711 (1994).

Robert Cori (1) * Pasquale Petrullo (2) ([dagger]) Domenico Senato (2) ([double dagger])

(1) LaBRI University Bordeaux 1, France

(2) Universita degli Studi della Basilicata, Italy

* Email: cori@labri.u-bordeaux.fr

([dagger]) Email :p.petrullo@gmail.com

([double dagger]) Email:domenico.senato@unibas.it

In [3] A. Bjorner, L. Lovasz and P. Schor have studied a solitary game called the chip-firing game which is closely related to the sandpile model of Dhar [6], arising in physics. In more recent papers some developments around this game were proposed. Musiker [11] introduced an unexpected relationship with elliptic curves, Norine and Baker [1] by means of an analogous game, proposed a Riemann-Roch formula for graphs, for which Cori and Le Borgne [5] presented a purely combinatorial description. An algebraic presentation of the theory can be found in [2] and [12]. In this paper we investigate this game, which we refer to as the toppling game, by exhibiting a wide range of connections with classical orthogonal polynomials and symmetric functions. We focus our attention on a noteworthy class of admissible moves, that we have called Yamanouchi moves. These moves are built up starting from suitable elementary moves, denoted by [T.sub.1], [T.sub.2], ..., [T.sub.n] and called topplings. A first crucial fact is that Yamanouchi moves are not invertible, this provides a partial order on the set of configurations and then principal order ideals may be considered. A second interesting point is that topplings can be seen as operators acting on the ring of formal series Z[[[x.sup.[+ or -]1.sub.1], [x.sup.[+ or -]1.sub.2], ..., [x.sup.[+ or -]1.sub.n]]], and in particular on the ring of polynomials Z[[x.sub.1], [x.sub.2], ..., [x.sub.n]]. Hence, each principal order ideal [H.sub.[alpha]] = [[beta] | [alpha] [[right arrow].sub.y] [beta]}, which stores all configurations obtained from a starting configuration a by means of a Yamanouchi move, may be identified with the series

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Topplings generate a group G, the toppling group, attached to any graph G. By setting [T.sub.[i]] = [T.sub.1][T.sub.2] ... [T.sub.i] we obtain algebraically independent elements spanning a subalgebra Z[[G].sub.[greater than or equal to]] of the group algebra Z[G]. We show there exists an operator [tau], with [[tau].sup.-1] [member of] Z[[G].sub.[greater than or equal to]], which depends on G but not on [alpha], such that [tau] x [x.sup.[alpha]] = [H.sub.[alpha]](x) and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By setting [T.sub.[i,j]] = [T.sub.[i]][T.sub.[i+1]] ... [T.sup.[j-1]] we obtain a further set of generators of Z[[G].sub.[greater than or equal to]] yielding a deformation of [tau] and a weighted version of [H.sub.[alpha]](x). More precisely, we recover

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and also we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where C([lambda]) counts the number of pairwise distinct decompositions in terms of the generators [T.sub.[i,j]] of the unique element [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in the toppling group G such that [beta] = [T.sup.[lambda]]([alpha]). Parameters [z.sub.1], [z.sub.2], [z.sub.3], q may be introduced in order to keep track of certain statistics [l.sub.1], [l.sub.2], [l.sub.3], d defined on the set of all decompositions of a given TA. Then, the following series can be considered,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Such a series satisfies [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since [??][([z.sub.1], [z.sub.2], [z.sub.3], q).sup.-1] = [??]([z.sub.1], [z.sub.2], (1 - q)[z.sub.3], q[(q - 1).sup.- 1]), then a combinatorial description of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is obtained for free. Moreover, [l.sub.1] [greater than or equal to] [l.sub.2] [greater than or equal to] [l.sub.3] [greater than or equal to] d [greater than or equal to] 0 implies that the coefficient of [x.sup.[beta]] in [[??].sub.[alpha]](x; [z.sub.1], [z.sub.2], [z.sub.3], q), as well as that in [[??].sub.[alpha]](x; [z.sub.1], [z.sub.2], [z.sub.3], q), is a polynomial with integer coefficients. Then, one can consider a projection [PI] such that [PI][x.sup.[beta]] = [x.sup.[beta]] if [beta] [member of] [N.sup.n], and [PI][x.sup.[beta]] = 0 otherwise. Hence both [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], with a ranging over [N.sup.n], are bases of Z[[z.sub.1], [z.sub.2], [z.sub.3], q][x]. Our interest in the toppling game is explained by focusing the attention on a very special family of graphs [{[L.sub.n]}.sub.n[greater than or equal to]1]. In this case, we prove that the polynomial sequence [{[PI][[??].sub.[alpha]](x; [z.sub.1], [z.sub.2], [z.sub.3], q)}.sub.[alpha]], via a suitable linear functional of umbral type [14], yields to a parametrized extension of classical orthogonal polynomials. More concretely, set [alpha] = (n - 1, n - 1, ..., n - 1) and let X = [X.sub.1], [X.sub.2], ..., [X.sub.n-1] denote i.i.d. random variables. Then, denote by [p.sub.n-1]([z.sub.1], [z.sub.2], [z.sub.2], q; t) the expected value of the polynomial obtained by replacing [x.sub.1] = t and [x.sub.i+1] = [X.sub.i] in [[??].sub.a](x; [z.sub.1], [z.sub.2], [z.sub.3], q):

[p.sub.n-1](t; [z.sub.1], [z.sub.2], [z.sub.3], q) = E[[??].sub.[alpha]](t, [X.sub.1], ..., [X.sub.n-1]; [z.sub.1], [z.sub.2], [z.sub.3], q).

The polynomial sequence {[p.sub.n](t; [z.sub.1], [z.sub.2], [z.sub.3], q)}n generalizes the orthogonal polynomial system associated with X [4, 13]. Classical cases, like Hermite, Laguerre, Poisson-Charlier, Chebyshev arise for [z.sub.1] = [z.sub.2] = [z.sub.3] = q = 1 when suitable random variables are chosen. Moreover, if we replace [x.sup.[beta]] with complete homogeneous symmetric functions [h.sub.[beta]](x) then an action of the toppling group on symmetric functions is obtained. In this context, when G = [L.sub.n] the action of the [T.sub.[i,j]]'s turns out to be closely related to that of raising operators [8] and this leads to a generalization of Hall-Littlewood symmetric functions [9] [{[R.sub.[lambda]](x; t)}.sub.[lambda]]. The toppling game not only provides a new elementary combinatorial basis for symmetric functions and orthogonal polynomials [10], but it also suggests further generalizations to analogous environments defined starting from further families of graphs [{[G.sub.n]}.sub.n].

2 The toppling game

Here and in the following, by a graph G = (V, E) we will mean a connected graph, with set of vertices V = {[[upsilon].sub.1], [[upsilon].sub.2], ..., [[upsilon].sub.n]}, and whose set of undirected edges E contains at most one edge {[[upsilon].sub.i], [[upsilon].sub.j]} for each pair ([[upsilon].sub.i], [[upsilon].sub.j]). Also, we say that [[upsilon].sub.i] and [[upsilon].sub.j] are neighbours whenever {[[upsilon].sub.i], [[upsilon].sub.j]} [member of] E. A configuration on G is a map, [alpha]: [[upsilon].sub.i] [member of] V [??] [alpha]([[upsilon].sub.i]) [member of] Z, associating each vertex [[upsilon].sub.i] with an integral weight [alpha]([[upsilon].sub.i]). If we set [[alpha].sub.i] = [alpha]([[upsilon].sub.i]) then we may identify any configuration a with the array ([[alpha].sup.1], [[alpha].sub.2], ..., [[alpha].sub.n]). We set [[epsilon].sub.i] = ([[delta].sub.i1], [[delta].sub.i2], ..., [[delta].sub.in]) so that [[epsilon].sub.i] is the configuration associating vi with 1 and [[upsilon].sub.j] with 0 if j [not equal to] i. A toppling of the vertex [[upsilon].sub.i] is a map [T.sup.G.sub.i]: [Z.sup.n] [right arrow] [Z.sup.n] defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

and [d.sub.i] = [absolute value of {[[upsilon].sub.j] | {[[upsilon].sub.i], [[upsilon].sub.j]} [member of] E}] is the degree of [[upsilon].sub.i]. Roughly speaking, the map [T.sup.G.sub.i] increases by 1 the weight [[alpha].sub.j] of each neighbour [[upsilon].sub.j] of [[upsilon].sub.i], and simultaneously decreases by [d.sub.i] the weight [a.sub.i]. As a trivial consequence we deduce that the size [absolute value of [alpha]] = [[alpha].sub.1] + [[alpha].sub.2] + ... + [[alpha].sub.n] of any [alpha] [member of] [Z.sup.n] is preserved by each toppling [T.sup.G.sub.i]. One may visualize topplings as special moves of a suitable combinatorial game defined on the graph G. More precisely, fix a starting configuration [alpha] = ([[alpha].sub.1], [[alpha].sub.2], ..., [[alpha].sub.n]) on the graph and label each vertex [[upsilon].sub.i] with its own weight [[alpha].sub.i]. By "firing" the vertex [[upsilon].sub.i] we change the configuration [alpha] into a new configuration [beta] = [T.sup.G.sub.i]([alpha]). A move of the toppling game simply is a finite sequence of fired vertices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], possibly not all distinct. Now, let us fix two configurations [alpha] and on a graph G and let us look for all possible moves changing [alpha] into [beta]. Also, assume that certain moves are forbidden in the game, so that each player is forced to perform only those moves that are in a given set M of admissible moves. Henceforth, by writing [alpha] [[right arrow].sub.M] [beta] we will mean that a can be changed into ft by means of a suitable admissible move in M. When useful, M will be identified with the corresponding set of monomials belonging to the free monoid [T.sup.*] generated by the alphabet T = {[T.sup.G.sub.1], [T.sup.G.sub.2], ..., [T.sup.G.sub.n]}. At this point a possible strategy of a player passes through the determination of those moves of minimal length (i.e. minimal number of fired vertices) that are admissible and that change [alpha] into [beta]. Therefore, the toppling game starts once a pair (G, M) is chosen, and two configurations [alpha], [beta] [member of] [Z.sup.n] are given so that [alpha] [[right arrow].sub.M] [beta]. Hence, the idea is to characterize, in an explicit way, the subset [M.sub.[alpha],[beta]] of all admissible moves changing a into ft, then to determine all moves in [M.sub.[alpha],[beta]] of minimal length. In the following we will focus our attention on a special set of admissible moves, which we name Yamanouchi moves, defined by Y = {[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is Yamanouchi}. Recall that a sequence, or word, w = [i.sub.1][i.sub.2] ... [i.sub.l] of positive integers is said to be Yamanouchi if and only if, for all k and for all i, the number occ(i, k), of occurrences of i in [i.sub.1][i.sub.2] ... [i.sub.k], satisfies occ(i, k) [greater than or equal to] occ(i + 1, k). If w = [i.sub.1][i.sub.2] ... [i.sub.l] then we set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and write [alpha] [[right arrow].sub.w] [beta] if and only if [beta] = [T.sup.G.sub.w]([alpha]). Associated with each Yamanouchi word w = [i.sub.1][i.sub.2] ... [i.sub.l] there is an integer partition [lambda](w) = ([[lambda].sub.1], [[lambda].sub.2], ...) whose ith part [[lambda].sub.i] equals the number occ(i, l) of occurrences of i in w. A suitable filling of the Young diagram of [lambda](w) yields a coding of w in terms of a standard Young tableau. More precisely, the Young tableau associated with w is the unique tableaux of shape [lambda](w) whose ith row (of length [[lambda].sub.i]) stores all j such that [w.sub.j] = i. This fixes a bijection between the set of all Yamanouchi words of l letters and the set of all standard Young tableaux of l boxes.

Proposition 1 If [alpha] [[right arrow].sub.w] [beta] and [lambda] = [lambda](w) then for all w' such that [lambda] = [lambda](w') we have [alpha] [[right arrow].sub.w'] [beta]. If [alpha] [[right arrow].sub.w] [beta] then the set of all Yamanouchi words extracted from all standard Young tableaux of shape [lambda](w) corresponds to moves in [[gamma].sub.[alpha],[beta]]. On the other hand the converse is not true. Hence, in order to get an explicit characterization of [[gamma].sub.[alpha],[beta]] and of those moves in yo,p of minimal length we need a slightly deeper investigation.

3 The toppling group

Assume a graph G = (V, E) is given and write [T.sub.1], [T.sub.2], ..., [T.sub.n] instead of [T.sup.G.sub.1], [T.sup.G.sub.2], ..., [T.sup.G.sub.n.] The toppling group associated with G is the group G generated by [T.sub.1], [T.sub.2], ..., [T.sub.n]. Let 1 denote its unity. By virtue of (1) we have [T.sub.i][T.sub.j] = [T.sub.j][T.sub.i] for all i, j, and then G is commutative. In particular, this says that all g [member of] G may be expressed in terms of topplings as a product of type [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for a suitable array of integers a = ([a.sub.1], [a.sub.2], ..., [a.sub.n]) [member of] [Z.sup.n]. On the other hand, it is also easy to verify that [T.sub.1][T.sub.2] ... [T.sub.n]([alpha]) = [alpha] for all [alpha], and then we have [T.sub.1][T.sub.2] ... [T.sub.n] = 1. As a consequence, all g [member of] G admit a presentation [T.sup.a] with a [member of] [N.sup.n]. In fact, if g = [T.sup.a] and if a [not member of] [N.sup.n] then let k = min{[a.sub.1], [a.sub.2], ..., [a.sub.n]} and set b = a - k([e.sub.1] + [e.sub.2] + ... + [e.sub.n]). Then b [member of] [N.sup.n] and [T.sup.b] = [T.sup.a][([T.sub.1][T.sub.2] ... [T.sub.n]).sup.k] = [T.sup.a] = g. The following lemma characterizes all presentations of the unity 1 in G.

Lemma 2 For all graphs G we have [T.sup.a] = 1 if and only if a = k([[epsilon].sub.1] + [[epsilon].sub.2] + ... + [[epsilon].sub.n]).

A first consequence of Lemma 2 is that apart from [T.sub.i][T.sub.j] = [T.sub.j][T.sub.i] and [T.sub.1][T.sub.2] ... [T.sub.n] = 1 there are not further relations satisfied by [T.sub.1], [T.sub.2], ..., [T.sub.n]. This provides a characterization of all distinct presentations of any element in the toppling group G.

Theorem 3 For all graphs G and for all a, b [member of] [N.sup.n] we have [T.sup.a] = [T.sup.b] if and only if there exists k [member of] Z such that b = a + k([[epsilon].sub.1] + [[epsilon].sub.2] + ... + [[epsilon].sub.n]).

Now, once a [member of] [N.sup.n] is chosen, we may set k = min{[a.sub.1], [a.sub.2], ..., [a.sub.n]} and define b = a- -k([[epsilon].sub.1] + [[epsilon].sub.2] + ... + [[epsilon].sub.n]). Clearly [T.sup.a] = [T.sup.b] and b is the unique array in Nn of minimal size with this property. In other terms, [T.sup.b] is the unique reduced decomposition of g = [T.sup.a].

Theorem 4 Let (G, Y) be a toppling game. If [alpha] [[right arrow].sub.y] [beta] then there exists a unique partition [lambda] = ([[lambda].sub.1], [[lambda].sub.2], ..., [[lambda].sub.l]) with l [less than or equal to] n - 1 parts such that [T.sup.[lambda]]([alpha]) = [beta]. Hence, [[gamma].sub.[alpha],[beta]] consists of exactly all Yamanuochi moves associated with standard Young tableaux of shape [mu] = [lambda] + k([[epsilon].sub.1] + [[epsilon].sub.1] + ... + [[epsilon].sub.n]), for a suitable k [member of] N. In particular, all minimal moves in [[gamma].sub.[alpha],[beta]] are the Yamanuochi moves associated with standard Young tableaux of shape [lambda].

4 A partial order on [Z.sup.n]

Our next goal is the following: we want to characterize in an explicit way the sets [H.sub.[alpha]] = {[beta] [member of] [Z.sup.n] | [alpha] [[right arrow].sub.y] [beta]} defined for all [alpha] [member of] [Z.sup.n]. To this aim, we denote by [I.sub.n] the set of all a = ([a.sub.1], [a.sub.2], ..., [a.sub.n]) [member of] [N.sup.n] such that [a.sub.i] = 0 for some i. Note that, for all g [member of] G there is exactly one a [member of] [I.sub.n] such that g = [T.sup.a]. In particular, [T.sup.a] is the reduced decomposition of g. This gives the following characterization of the group algebra Z[G].

Theorem 5 We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and in particular

Z[G] [congruent to] Z[[x.sub.1], [x.sub.2], ..., [x.sub.n]]/<1 - [x.sub.1][x.sub.2] ... [x.sub.n]>,

with <1 - [x.sub.1][x.sub.2] ... [x.sub.n]> denoting the principal ideal generated by 1 - [x.sub.1][x.sub.2] ... [x.sub.n].

We consider not only elements in Z[G] but we also admit formal series in [T.sub.1], [T.sub.2], ..., [T.sub.n]. In particular we set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If we associate each [alpha] [member of] [Z.sup.n] with a monomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] then we may translate the action of G on [Z.sup.n] into an action of Z[[G]], and in particular of Z[G], on the ring of formal series

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This is done by setting [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all a [member of] [N.sup.n] and for all a [member of] [Z.sup.n]. Clearly, knowing the set [H.sub.[alpha]] = {[beta] [member of] [Z.sup.n] | [alpha] [[right arrow].sub.y] [beta]} is equivalent to knowing the formal series

[H.sub.[alpha]](x) = [summation over ([alpha][right arrow][gamma][beta])][x.sup.[beta]].

In the following we will determine a special element [tau] [member of] Z[[G]] satisfying [tau] x [x.sup.[alpha]] = [H.sub.[alpha]](x). Before doing that we introduce a new relation [[less than or equal to].sub.G] on [Z.sup.n]: set [beta] [[less than or equal to].sub.G] [alpha] if and only if [beta] = [T.sup.[lambda]](a) with [[lambda].sub.1] [greater than or equal to] [[lambda].sub.2] [greater than or equal to] ... [greater than or equal to] [[lambda].sub.n] [greater than or equal to] 0. Clearly, if [[lambda].sub.n] = 0 then we may define [mu] = [lambda] - [[lambda].sub.n]([[epsilon].sub.1] + [[epsilon].sub.2] + ... + [[epsilon].sub.n]) so that [T.sup.[lambda]](a) = [T.sup.[lambda]]([beta]) and [T.sup.[mu]] is a reduced decomposition for [T.sup.[lambda]]. Note that [mu] is an integer partition with at most n - 1 parts. Henceforth we will denote by [P.sub.n] the set of all integer partitions with at most n - 1 parts or, equivalently the subset of all [lambda]'s in [I.sub.n] such that [[lambda].sub.1] [greater than or equal to] [[lambda].sub.2] [greater than or equal to] ... [greater than or equal to] [[lambda].sub.n]. The following proposition makes explicit the relation between the relation [[less than or equal to].sub.G] and the toppling game.

Proposition 6 For all graphs G the relation [[less than or equal to].sub.G] is a partial order on [Z.sup.n]. Moreover, [[less than or equal to].sub.G] and [right arrow][gamma] agree on Zn.

Proposition 6 assures us that the set [H.sub.[alpha]] is nothing but the order ideal generated by [alpha], that is [H.sub.[alpha]] = {[beta] | [beta] [[less than or equal to].sub.G] [alpha]}. Let us consider the following element in Z[[G]]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and let it act on the monomial [x.sup.[alpha]]. Being [beta] = [T.sup.[lambda]]([alpha]) for at most one [lambda] [member of] [P.sub.n], then we recover

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The crucial point is that a closed expression of [tau] is available by introducing suitable elements of G. More precisely, we define

[T.sub.[i]] = [T.sub.1][T.sub.2] ... [T.sub.i] for all i = 1, 2, ..., n - 1.

Note that [T.sub.[i]] may be thought of as a Yamanouchi move associated with a Young standard tableau of one column filled with 1, 2, ..., i.

Theorem 7 Let [lambda] [member of] [P.sub.n] and denote by [lambda]' = ([[lambda]'.sub.1], [[lambda]'.sub.2], ..., [[lambda]'.sub.l]) the conjugate of A. Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Corollary 8 We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now, we may write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Moreover, straightforward computations will prove the following theorem.

Theorem 9 For each graph G there exists a formal series t(x) [member of] Z [[[x.sup.[+ or -]1.sub.1], [x.sup.[+ or - ]1.sub.2], ..., [x.sup.[+ or -]1.sub.n]] such that [H.sub.[alpha]](x) = [tau](x)[x.sup.[alpha]], for all [alpha] [member of] [Z.sup.n].

5 A special set of Yamanouchi moves

If G is the toppling group associated with a graph G then we set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Clearly Z[[G].sub.[greater than or equal to]] is a subalgebra of Z[G] and Theorem 7 assures us it is exactly the subalgebra generated by [T.sub.[1]], [T.sub.[2]], ..., [T.sub.[n-1]]. Let us consider a wider set of generators of Z[G[].sub.[greater than or equal to]] defined by [T.sub.[i,j]] = [T.sub.[i]][T.sub.[i+1]] ... [T.sub.[j-1]] for all 1 [less than or equal to] i < j [less than or equal to] n. Note that each [T.sub.[i,j]] is a Yamanouchi move associated with a tableau whose shape consists of consecutive integers. Obviously [T.sub.[i]] = [T.sub.[i,i+1]] so that the [T.sub.[i,j]]'s generate the whole Z[[G].sub.[greater than or equal to]]. On the other hand, the presentation of any g [member of] G as a product of these generators is in general not unique. In order to find a reduced decomposition of g = [T.sup.[lambda]], that is a presentation that involves a minimal number of generators, we write [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then rearrange and associate so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and each product ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) consists of an increasing sequence of consecutive integers. Thus, a reduced decomposition of TA is given by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Example 1 If [lambda] = (8, 7, 4, 3, 2, 2, 1) then [lambda]' = (7, 6, 4, 3, 2, 2, 2, 1). We recover

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A reduced decomposition of [T.sup.[lambda]] is given [T.sub.[1,5]][T.sup.2.sub.[2,3]][T.sub.[6,8]].

A decomposition [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is said to be square free if and only if each generator occurs at most once. For instance, [T.sub.[1,2]][T.sub.[1,3]][T.sub.[2,5]] is square free but [T.sub.[1,2]][T.sub.[1,2]][T.sub.[2,3]][T.sub.[2,5]] is not square free. Also, note that [T.sub.[1,2]][T.sub.[1,3]][T.sub.[2,5]] = [T.sub.[1,2]][T.sub.[1,2]][T.sub.[2,3]][T.sub.[2,5]] so that a given element in Z[[G].sub.[greater than or equal to]] may have both square free and not square free decompositions. Now, consider the operator [??] in Z[[G]] defined by

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

Note that [??] is the analogue of [tau] for the generators [T.sub.[i,j]]'s. Moreover, we recover

with C([lambda]) being the number of pairwise distinct presentations of g = [T.sup.[lambda]] in terms of the generators [T.sub.[i,j]]'s. Finally, we may write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

with [lambda] denoting the unique element in [P.sub.n] such that [beta] = [T.sup.[lambda]]([alpha]).

6 The graph Ln and classical orthogonal polynomials

In this section we restrict our attention to a special family of graphs, denoted by [{[L.sub.n]}.sub.n], and defined by [L.sub.n] = ([V.sub.n], [E.sub.n]), with [V.sub.n] = {[[upsilon].sub.1], [[upsilon].sub.2], ..., [[upsilon].sub.n]} and [E.sub.n] = {{[[upsilon].sub.1], [[upsilon].sub.2]}, {[[upsilon].sub.2], [[upsilon].sub.3]}, ..., {[[upsilon].sub.n-1], [[upsilon].sub.n]}}, for all n [greater than or equal to] 1. Now, assume a linear functional L: C[t] [right arrow] C is given. An orthogonal polynomial system associated with L is a polynomial sequence [{[p.sub.n](t)}.sub.n], with deg [p.sub.n] = n for all n [member of] N, such that [Lp.sub.n](t)[p.sub.m](t) = 0 if and only if n [not equal to] m. We refer to [4] for a background on this subject. The toppling game performed on the [L.sub.n]'s gives rise to a nice combinatorial framework for orthogonal polynomial systems. Consider the unique [p.sub.[alpha]](x) such that [x.sup.[alpha]] = [??] x [p.sub.[alpha]](x), or equivalently

[p.sub.[alpha]](x) = [[??].sup.-1] x [x.sub.[alpha]]. (3)

Observe that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where the sum is taken over all square free decompositions in G. Because the size of a configuration is preserved by the toppling game, [p.sub.[alpha]](x) is a homogeneous polynomial of degree [absolute value of [alpha]]. Moreover, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

so that [beta] ranges over all configurations that can be obtained from [alpha] by means of a square free Yamanouchi move [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Also, the coefficient [p.sub.[alpha],[beta]] of [x.sup.[beta]] in [p.sub.a[alpha](x) has the following combinatorial description,

[p.sub.[alpha],[beta]] = E[(-1).sup.l], (4)

where l ranges over all lengths of all square free Yamanouchi moves changing a into [beta]. In order to manipulate polynomials with an arbitrary large number of variables at the same time we set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now, let E: C[[x.sub.1], [x.sub.2], ...] [right arrow] C denote a map such that

1. for all n [greater than or equal to] 1 the restriction E: C[[x.sub.1], [x.sub.2], ..., [x.sub.n]] [right arrow] C is a linear functional;

2. for all n [greater than or equal to] 1, for all p [member of] C[[x.sub.1], [x.sub.2], ..., [x.sub.n]] and for all [sigma] [member of] [G.sub.n], we have Ep([x.sub.[sigma](1)], [x.sub.[sigma](2)], ..., [x.sub.[sigma](n)]) = Ep([x.sub.1], [x.sub.2], ..., [x.sub.n]).

Henceforth, we will call any functional of this type a symmetric functional. Once a symmetric functional E is given then we may define conditional operators [E.sub.i]: C[[x.sub.1], [x.sub.2], ...] [right arrow] C[[x.sub.i]] for all i [greater than or equal to] 1. Each [E.sub.i] is defined by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all [alpha] [member of] [N.sup.n]. Roughly speaking, each [E.sub.i] acts on C[[x.sub.1], ..., [x.sub.i-1], [x.sub.i+1], ...] as E acts, and fixes each polynomial in C[[x.sub.i]].

Remark 1 If [X.sub.1], [X.sub.2], ... is an infinite sequence of i.i.d. random variables, and if E is the expectation functional, then E: C[[X.sub.1], [X.sub.2], ...] [right arrow] C gives an example of symmetric functional.

Set G = [L.sub.n] and choose [alpha] [member of] [Z.sup.n]. In this case it is not too difficult to see that [T.sub.[i]] x [x.sup.[alpha]] = [x.sup.[alpha]][x.sub.i+1][x.sup.-1.sub.i] for all i = 1, 2, ..., n - 1. Hence, by means of straightforward computations we recover

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If [p.sub.n](x) is defined as in (3) with [alpha] = (n - 1, n - 1, ..., n - 1), then we recover

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, if [E.sub.1]: C[[x.sub.1], [x.sub.2], ...] [right arrow] C[[x.sub.1]] is a conditional operator associated with a symmetric functional E: C[[x.sub.1], [x.sub.2], ...] [right arrow] C, then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

with [e.sub.i]([x.sub.2], [x.sub.3], ..., [x.sub.n]) denoting the ith elementary symmetric polynomial in [x.sub.2], [x.sub.3], ..., [x.sub.n]. This implies that [p.sub.n-1]([x.sub.1]) is a polynomial in [x.sub.1] of degree at most n - 1. In particular, we have deg [p.sub.n] = n - 1 if and only if

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

On the other hand, since E is symmetric then we may replace each [x.sub.i] with [x.sub.i-1] in (5) without changing its value. Then we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This last condition, if satisfied for all n, will assures deg [p.sub.n] = n.

Theorem 10 (Orthogonal polynomial systems) Let E: C[[x.sub.1], [x.sub.2], ...] [right arrow] C be a symmetric functional, set G = [L.sub.n], and assume

E[[??].sup.-1] x [([x.sub.1][x.sub.2] ... [x.sub.n-1]).sup.n] [not equal to] 0 for all n [greater than or equal to] 1.

Then, the polynomial sequence [{[p.sub.n](t)}.sub.n] defined by

[p.sub.n-1]([x.sub.1]) = [E.sub.1][??] x [([x.sub.1][x.sub.2] ... [x.sub.n]).sup.n-1] [not equal to] 0 for all n [greater than or equal to] 1, satisfies [Ep.sub.n]([x.sub.1])[p.sub.m]([x.sub.1]) = 0 if and only n = m.

Theorem 10 gives us a general method to construct all orthogonal systems associated with a given linear functional L, provided they exist. In fact, given L: C[t] [right arrow] C, we consider the unique symmetric functional E: C[[x.sub.1], [x.sub.2], ...] [right arrow] C such that [Ex.sup.k.sub.i] = [Lt.sup.k], for all i [greater than or equal to] 1 and for all k [greater than or equal to] 0. Also, we set [a.sub.[alpha]] = [Ex.sup.[alpha]] for all [alpha] [member of] [Z.sup.n]. Hence, an orthogonal polynomial system [{[p.sub.n](t)}.sub.n] associated with L exists if and only if [E[??].sup.-1] [([x.sub.1][x.sub.2] ... [x.sub.n-1]).sup.n] [not equal to] 0 for all n [greater than or equal to] 1. Moreover, it is obtained by setting [p.sub.n-1]([x.sub.1]) = [E.sub.1][[??].sup.-1][([x.sub.1][x.sub.2] ... [x.sub.n]).sup.n-1]. So, the following combinatorial formula for [p.sub.n-1](t) is provided:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [alpha] = (n - 1, n - 1, ..., n - 1), [beta] ranges over all configurations that can be obtained from a by means of square free Yamanouchi move, and [p.sub.[alpha],[beta]] is the coefficient (4).

7 Statistics on the toppling group

In this section we focus our attention on the distribution of certain statistics [l.sub.1], [l.sub.2], [l.sub.3], d defined on the decompositions of elements in the toppling group in terms of the three families of generators {[T.sub.i] | i = 1, 2, ..., n}, {[T.sub.[i]] | i = 1, 2, ..., n - 1} and {[T.sub.[i,j]] | 1 [less than or equal to] i < j [less than or equal to] n}. More precisely, each [T.sup.[lambda]] [member of] G, [lambda] [member of] [P.sub.n], admits a unique expression, up to order of the [T.sub.i]'s, of type g = [T.sup.[lambda]]. This expression involves [l.sub.1] generators, and in particular [l.sub.1] equals the size of the partition [lambda]. Analogously, [T.sup.[lambda]] can be written in a unique way, up to order, in terms of the [T.sub.[i]]'s. In particular, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and this involves [l.sub.2] = [[lambda].sub.1] generators. On the other hand, there are C([lambda]) ways of writing [T.sup.[lambda]] as a product of generators [T.sub.[i,j]]'s. Each of such expressions involves a certain number, say [l.sub.3], of generators. Among these d [less than or equal to] [l.sub.3] are pairwise distinct.

Theorem 11 Set

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

Then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where the sum ranges over all pairwise distinct decompositions [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We may define a parametrized version of the series [[??].sub.[alpha]](x) by setting

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

We recover

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where the coefficient of [x.sup.[beta]] stores the value of [l.sub.1], [l.sub.2], [l.sub.3], d relative to all pairwise distinct decompositions of the unique [T.sup.[lambda]] such that [beta] = [T.sup.[lambda]]([alpha]). As a consequence we obtain a parameterized extension of orthogonal polynomials. In fact, for all n [greater than or equal to] 1 and for all [alpha] [member of] [Z.sup.n] set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since [??][([z.sub.1], [z.sub.2], [z.sub.3], q).sup.-1] = [??]([z.sub.1], [z.sub.2], (1 - q)[z.sub.3], q[(q - 1).sup.- 1]) then the following combinatorial description is obtained:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Since [l.sub.1] [less than or equal to] [l.sub.2] [greater than or equal to] [l.sub.3] [greater than or equal to] d [greater than or equal to] 0 then the coefficient of [x.sup.[beta]] in [[??].sub.[alpha]](x; [z.sub.1], [z.sub.2], [z.sub.3], q) is a polynomial with integer coefficients. By setting [z.sub.1] = [z.sub.2] = [z.sub.3] = q = 1 we have a non-zero contribution only for decompositions such that [l.sub.3] - d = 0, that is square free decompositions. At this point, one can consider a projection [PI] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and then both [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], with [alpha] ranging over [N.sup.n], are bases of Z[[z.sub.1], [z.sub.2], [z.sub.3], q][x]. By defining a suitable symmetric functional E, and by setting [p.sub.n- 1]([x.sub.1]; [z.sub.1], [z.sub.2], [z.sub.3], q) = [E.sub.1][??][([z.sub.1], [z.sub.2], [z.sub.3], q).sup.-1] x [([x.sub.1][x.sub.2] ... [x.sub.n]).sup.n-1] we obtain a polynomial sequence [{[p.sub.n](t; [z.sub.1], [z.sub.2], [z.sub.3], q)}.sub.n] that generalizes classical orthogonal polynomials.

Example 2 Hermite polynomials [{[H.sub.n](t)}.sub.n] forms an orthogonal polynomial system with respect to the linear functional L defined by [Lt.sup.k] = [EX.sup.k], where X is a Gaussian random variable. Assume X = [X.sub.1], [X.sub.2], ... are independent Gaussian random variables and set [x.sub.1] = t and [x.sub.i] = [X.sub.i-1]. Then the polynomial sequence {[p.sub.n](t; [z.sub.1], [z.sub.2], [z.sub.3], q)}n defined by

[p.sub.n-1](t; [z.sub.1], [z.sub.2], [z.sub.3], q) = E[PI][[??].sub.[alpha]](t, [X.sub.1], [X.sub.2], ..., [X.sub.n-1]; [z.sub.1], [z.sub.2], (1 - q)[z.sub.3], q/q - 1),

with [alpha] = (n - 1 , n - 1, ..., n - 1) generalizes Hermite polynomials.

8 New combinatorics for H-L symmetric polynomials

The toppling group G acts on the ring [LAMBDA](x; [z.sub.1], [z.sub.2], [z.sub.3], q), of symmetric polynomials in [x.sub.1], [x.sub.2], ..., [x.sub.n] with coefficients in Z[[z.sub.1], [z.sub.2], [z.sub.3], q]. In fact, let [h.sub.i](x) denote the ith complete homogeneous symmetric polynomial, and for all [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. By assuming [h.sub.i](x) = 0 for i < 0 and [h.sub.0](x) = 1, we set

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

Finally, if [alpha] is a partition and if [s.sub.[alpha]](x) is a Schur polynomial then the symmetric polynomials [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] may be considered.

Theorem 12 For any graph G the sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], with a raging over all integer partitions, are bases of the ring [LAMBDA](x; [z.sub.1], [z.sub.2], [z.sub.3], q).

Again, the special case G = [L.sub.n] leads to some interesting consequences. In fact, we recover [T.sub.[i,j]] x [h.sub.[alpha]](x) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], so that [T.sub.[i,j]] acts as a "lowering operator" [R.sub.ji] (see [9], p.214). In particular this implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now, recall that the Hall-Littlewood symmetric polynomial [R.sub.[alpha]](x; t), [alpha] being a partition, satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This implies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Remark 2 Hence, [[??].sub.a](x; [z.sub.1], [z.sub.2], [z.sub.3], q) extends to four parameters Hall-Littlewood symmetric polynomials, and then several classical bases of symmetric functions such as Schur functions (t = 0). From this point of view they share some analogy with Macdonald symmetric polynomials. Moreover, the toppling game also yields several families of symmetric functions, each one attached to a graph G and then a general theory extending the classical case (G = [L.sub.n]) could be carried out.

Remark 3 Lowering operators [R.sub.ji]'s have a counterpart [R.sub.ij]'s called "raising operators"[8, 9]. In our setting they will arise as generators, say the [T.sub.[j,i]]'s, of the subalgebra Z[[G].sub.[less than or equal to]] spanned over Z by all [T.sup.[lambda]], with 0 [less than or equal to] [[lambda].sub.1] [less than or equal to] [[lambda].sub.2] ... [less than or equal to] [[lambda].sub.n].

References

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

[2] N. Biggs Chip-firing and the critical group of a graph J. of Algebraic Comb. 9, 25-45 (1999).

[3] A. Bjorner, L. Lovasz, P. Schor, Chip-firing game on graphs. Europ. J.of Comb. 12, 283-291 (1991).

[4] T.S. Chiahara, An introduction to Orthogonal polynomials. Mathematics and its applications - A series of monographs and texts 13, (1978).

[5] R. Cori, Y. Le Borgne, The Riemann-Roch theorem for graphs and the rank in complete graphs. Preprint, pp. 35 (2013).

[6] D. Dhar, Self-organized critical state of the sandpile automaton models. Phys. Rev. Lett., 64, 1613-1616 (1990.)

[7] D. Dhar, P. Ruelle, S. Sen, and D. Verma. Algebraic aspects of abelian sandpile model. J. Phys. A A28, 805-831 (1995).

[8] A. Garsia, Orthogonality of Milne's polynomials and raising operators. Discrete Mathematics 99, 247-264 (1992).

[9] I.G. Macdonald, Symmetric functions and Hall polynomials. Oxford Mathematical Monograph. Oxford University Press (1995).

[10] I.G. Macdonald, Affine Hecke algebras and orthogonal polynomials. Cambridge Tracts in Mathematics 157, Cambridge University Press (2003).

[11] G. Musiker, The critical groups of a family of graphs and elliptic curves over finite fields. Journal of Algebraic Combinatorics 30, 255-276 (2009).

[12] D. Perkinson, J. Perlman, and J. Wilmes. Primer for the algebraic geometry of sandpiles. preprint, arXiv:1112.6163, (2011).

[13] P. Petrullo, D. Senato, R. Simone, Orthogonal polynomials through the invarinat theory of binary forms. Preprint (2014).

[14] G.-C. Rota and B. Taylor, The classical umbral calculus. SIAM Journal of Mathematical Analysis 25(2), 694-711 (1994).

Robert Cori (1) * Pasquale Petrullo (2) ([dagger]) Domenico Senato (2) ([double dagger])

(1) LaBRI University Bordeaux 1, France

(2) Universita degli Studi della Basilicata, Italy

* Email: cori@labri.u-bordeaux.fr

([dagger]) Email :p.petrullo@gmail.com

([double dagger]) Email:domenico.senato@unibas.it

Printer friendly Cite/link Email Feedback | |

Author: | Cori, Robert; Petrullo, Pasquale; Senato, Domenico |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Date: | Jan 1, 2014 |

Words: | 6864 |

Previous Article: | Deformations of Weyl's denominator formula: six conjectures and one result. |

Next Article: | Centralizers of the infinite symmetric group. |

Topics: |