The Chip Firing Game (CFG) is a classical discrete dynamical model, used in physics, economics and computer science. We give here the definition of a CFG, expose the main known results, and show how some known models can be encoded as CFGs.
A Chip Firing Game (CFG) is defined by:
The evolution rule of the game is the following: if a vertex contains at least as many chips as its outgoing degree, we can fire this vertex, i.e. we can move one chip along each outgoing edge to the corresponding vertex.
For some CFGs, every execution is finite (we mainly study these ones).
There is then no cycle in the set of reachable configurations, so it is
an order, and more, it is a lattice [LP00].
We give here an example of a CFG and the lattice of its reachable configurations.
The graph with its initial configuration is on top.
Moreover, we know that this lattice is lower locally distributive (LLD): the interval between an element and the lower bound of all its immediate successors is a hypercube.
Some known discrete dynamical models can be encoded as CFGs, so that they share their properties (including convergence).
We give here one example, the Sand Pile Model (SPM):
SPM(n) can be encoded as a CFG in the following way: we take a graph
of n+1 vertices on a line, with edges from each vertex to its predecessor
and its successor, except for the first vertex, which is a sink. We start
with n chips in the second vertex.
Each vertex (except the sink) represents a column of SPM, and each configuration
represents the difference in the number of grains in the corresponding
column and the one to the right.
We give here for example SPM(7) and the corresponding CFG.
Some variations on SPM can also be encoded as CFGs, as well as the Abelian Sand Pile Model.