Printer Friendly

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
COPYRIGHT 2014 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
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:

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