•  » Home  

Research

•  » Sandpiles  
•  » Sand automata  
•  » Publications  

RECIF

•  » Seminars  

» Sandpiles

---

2. Definitions

We recall here the notions and results introduced in [2, 3].

2.1 Definitions

A sandpile (or configuration) is a finite sequence of non-zero integers c = (c₁, ... , c_l), where l is the length of the configuration.

A sandpile system is a discrete dynamic system working on these configurations. It is defined by local rules which allow a configuration to evolve. For example, the most common model, SPM (Sand Pile Model [2]), is defined by a vertical rule: as soon as a column c_i is at least 2 grains higher than its right neighbor c_i+1, the leftmost column can lose a grain on its right.

Vertical rule of SPM.

We obtain a new configuration, and after iterating on this new configuration we have the orbit of the initial configuration: a finite path without cycles. Remark that sometimes the rule can be applied at different places at the same time. If we draw all the orbits on a edge-directed graph (the vertices are the configurations, and there is an edge between two vertices if the second one can be obtained by applying the local rule somewhere in the first one) we define the orbit graph.

Orbit graph of the initial configuration (8) for SPM.

As shown on this example, there is always no more than one fixed point. No matter where the rule is applied, the fixed point is the same (this fact is proved in the next subsection).

There is also another set of common models, IPM(k) (Ice Pile Model [3]), which is in fact a generalization of SPM. They contain the vertical rule, and an horizontal rule which allow the grains to slide. If for a given k there exists i < j such that c_i = c_i+1 + 1 = ... = c_j + 1 = c_j+1 + 2, j - i < k, then a grain can move from column i to column j+1.

Horizontal rule of IPM(k).

With this definition, clearly SPM is exactly IPM(1). Depending on the context, SPM will either be considered as a particular case of IPM(k), or as a complete model when the general statement is too complex. One can also define orbit graphs for IPM(k) in the same manner as for SPM, in this case also it appears that there is only one fixed point.

Orbit graph of the initial configuration (7) for IPM(3).

2.2 Known results

Theorem 1 [3]. For all integers k, n, the orbit graph of (n) for IPM(k) is a finite lattice.

This very important result implies that there only one fixed point for a given initial configuration with one column, independently on the path chosen. The following lemma completes this result by characterizing the elements of the graph.

Lemma 2 [3]. For all k, n, a configuration c with n grains belongs to the orbit graph of (n) for IPM(k) if and only if for all i < j, j - i ≤ k(c_i - c_j + 1).

In the SPM case, this lemma means that a configuration is reachable if and only if it is decreasing, and if between two consecutive plateaus there is at least a cliff. In other words, if there are two plateaus one of them must be destroyed by an avalanche in-between.

This is also how one can understand the statement of the lemma for IPM(k): between two plateaus of size k+1, one of the rules must be applicable in order that the configuration can be reached.

Then it is possible to describe the fixed point of (n) for IPM(k), since it is the only decreasing configuration with n grains which has only plateaus of length k, and at most one of size k+1 and one of size k' < k at the top. For example, the fixed point of (18) for IPM(2) is as shown:

Fixed point of (18) for IPM(2).

For a precise description of the structure of the fixed points, please refer to [3].

Finally the last known results deal with the maximal transient length (number of iterations before the fixed point is reached) for the models IPM(k), the exact formulas can be found in [3]. Remark that for SPM, all paths have the same length, but in all other cases, the minimal length is still unknown.

---

Bibliography

[1]	P. Bak, C. Tang, et K. Wiesenfeld. Self-organized criticality. Physical Review A, 38(1):364−374, 1988.
[2]	E. Goles and M. A. Kiwi. Games on line graphs and sand piles. Theoretical Computer Science, 115(2):321−349, 1993.
[3]	E. Goles, M. Morvan, and H. D. Phan. Sand piles and order structure of integer partitions. Discrete Applied Mathematics, 117:51−64, 2002.
[4]	T. Brylawski. The lattice of integer partitions. Discrete mathematics, 6:201−219, 1973.
[5]	E. Formenti and B. Masson. On Computing Fixed Points for Generalized Sandpiles. International Journal of Unconventional Computing, 2(1):13−25, Old City Publishing, 2006.
[6]	E. Formenti and B. Masson. A note on fixed points of generalized ice pile models. International Journal of Unconventional Computing, 2(2), Old City Publishing, 2006.
[7]	E. Formenti, B. Masson and T. Pisokas. On symmetric sandpiles. In Cellular Automata for Research and Industry (ACRI 2006), Lecture Notes in Computer Sciences, Springer-Verlag, 2006.