The structure of a linear chip firing game and related models

Eric Goles, Michel Morvan, Ha Duong Phan

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


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 worst classical one, introduced by Brylawski (Discrete Math. 6 (1973) 201) induces a lattice structure LB(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 LB(n) in suborders, each one is associated to a fixed point for the SPM rule. In the second part, we extend the SPM rule in a natural way and obtain a model called Linear Chip Firing Game (Theoret. Comput. Sci. 115 (1993) 321). 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 θ, denoted by L(n,θ), which form a decreasing sequence of lattices when θ varies in [-n+2,n]. For each θ, we characterize the fixed point of L(n,θ) and give the value of its maximal sized chain's length. We also note that L(n,-n+2) is the lattice of all compositions of n.

Original languageEnglish
Pages (from-to)827-841
Number of pages15
JournalTheoretical Computer Science
Issue number1-2
StatePublished - 6 Jan 2002
Externally publishedYes


  • Fixed point
  • Integer partition
  • Lattice
  • Linear chip firing game
  • Model of Brylawski
  • Sand pile model


Dive into the research topics of 'The structure of a linear chip firing game and related models'. Together they form a unique fingerprint.

Cite this