The Sand Piles Model (SPM) is a special case of the more general Chip Firing Game (CFG), which was introduced by Spencer in 1986 to study some ``balancing game''. There are a lot of specializations and extensions of this model which have been introduced and studied under different names, different aspects and with different approaches. The SPM problem came from the Self-Organized Criticality (SOC) problem introduced by Bak, Tang and Wiesenfield in 1987. Many approaches of the study of such systems have been developed like the algebraic approach by Dhar (1998), Cori, Rossin (1998), the game theory by Bjorner, Lov\'asz and Shor (1991), the language theory approach by Bjorner and Zieler (1991), etc
In the Sand Piles Model (introduced by Goles and Kiwi, 1993), a sand pile is represented by an ordered partition of an integer n i.e. a decreasing sequence a = (a_1, ... ,a_n) of sum n, and the movement of a sand grain respects the following rule:
Rule 1 (vertical rule): one grain can move form a columm to the next columm if the difference of height of these two columms is greater than or equal to 2.
In the model L_B (introduced by Brylawski, 1973), the movement of a sand grain respects Rule 1 and Rule 2, which is described as follows:
Rule 2 (horizontal rule): If a columm containing (p+1) grains, is followed by a sequence of columms containing p grains and then one columm containing (p-1) grains, then one grain of the first columm can slip to the last columm.
The research object of these models is the order structure defined on the set of all partitions obtained from the initial one (n,0,...,0). This order is defined as follow: a partition b is smaller than a if b can be obtained from a.
Here are exemples of lattice SPM(7) and lattice L_B(7):
For bigger examples, see Images.
From 1995, Michel Morvan, Eric Goles, Matthieu Latapy, Roberto Mantaci and Ha Duong Phan have proposed the lattice approach to study the dynamical models. Almost all systems studied in this work have a linear topology. They have extended the classical models SPM and L_B to obtain more general models.
Some extensions
The model IPM (Ice Pile Model) is obtained by relaxing the constraint of locality. In the model IPM(n,k), one grain can move by applying Rule 1 or by applying Rule 2 with the additional constraint that the distance between two affected columms is smaller than k.
The model CFG(n,m) (Chip Firing Game) is obtained by modifying the number of grains which move. In the model CFG(n,m), at each time, m grains move from one columm to the m nearest columms at its right under the condition that the obtained sequence is still decreasing.
The models L(\theta) of compositions is obtained by relaxing the constraint of decreasing sequence. In the model L(\theta), one grain can move from one columm to the next columm with the condition that the height difference between two adjacent columms is greater than or equal to \theta. Here, one can obtain non-decreasing sequences (i.e. compositions). A special case extended from L(1) is the "Game of Cards". This is a problem which appeared in the study of distributed systems.
The model SPM in its infinite version, where we consider a columm with an infinite number of grains as the initial configuration, and where we iterate the Rule 1.
Some interesting results
Almost all these models have a lattice structure. In some cases (for example SPM, IPM, L_B), there are explicit formulas for the fixed point, the time to reach a partition, the distance between two partitions in the lattice, ... In some other cases (for example CFG(n,m), "Game of Cards", ...), the obtained lattice has a strong structure: it is a lower locally distributive lattice. In the infinite version, the model SPM and the model L_B have a recursive structure which makes it possible to give an interesting construction algorithm. Moreover, for a given n, the set of all IPM(n,k) form an increasing sequence of lattices with respect to the suborder relation; and the set of all L(\theta) form such a sequence too.
Here is an exemple of the sequence of IPM with n=8.
