Mathematics – Combinatorics
Scientific paper
2000-10-31
Mathematics
Combinatorics
19 pages, 4 figures. Submitted See also: http://www.liafa.jussieu.fr/~phan/anglais/public
Scientific paper
In this paper, we study the dynamics of sand grains falling in sand piles. Usually sand piles are characterized by a decreasing integer partition and grain moves are described in terms of transitions between such partitions. We study here four main transition rules. The more classical one, introduced by Brylawski (1973) induces a lattice structure $L_B (n)$ (called dominance ordering) between decreasing partitions of a given integer n. We prove that a more restrictive transition rule, called SPM rule, induces a natural partition of L_B (n) in suborders, each one associated to a fixed point for SPM rule. In the second part, we extend the SPM rule in a natural way and obtain a model called Chip Firing Game (Goles and Kiwi, 1993). We prove that this new model has interesting properties: the induced order is a lattice, a natural greedoid can be associated to the model and it also defines a strongly convergent game. In the last section, we generalize the SPM rule in another way and obtain other lattice structure parametrized by some t: L(n,t), which form for -n+2 <= t <= n a decreasing sequence of lattices. For each t, we characterize the fixed point of L(n,t) and give the value of its maximal sized chain's lenght. We also note that L(n,-n+2) is the lattice of all compositions of n.
Goles Eric
Morvan Michel
Phan Ha Duong
No associations
LandOfFree
The structure of Chip Firing Games and related models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The structure of Chip Firing Games and related models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The structure of Chip Firing Games and related models will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-446822