Chip-firing game


The chip-firing game is a one-player game on a graph which was invented around 1983 and since has become an important part of the study of structural combinatorics.

Definition

Let the finite graph G be connected and loopless, with vertices V =. Let deg be the degree of a vertex, and e the number of edges between vertices v and w. A configuration or state of the game is defined by assigning each vertex a nonnegative integer s, representing the number of chips on this vertex. A move starts with selecting a vertex w which has at least as many chips as its degree: s ≥ deg. The vertex w is fired, moving one chip from w along each incident edge to a neighbouring vertex, producing a new configuration defined by:
and for v ≠ w,
A state in which no further firing is possible is a stable state. Starting from an initial configuration, the game proceeds with the following results.
In a variant form of chip-firing closely related to the sandpile model, also known as the dollar game, a single special vertex q is designated as the bank, and is allowed to go into debt, taking a negative integer value s < 0. If any other vertex can fire, the bank cannot fire, only collecting chips. Eventually, q will accumulate so many chips that no other vertex can fire: only in such a state, vertex q can fire chips to neighbouring vertices to "jump start the economy".
The set of states which are stable and recurrent for this game can be given the structure of an abelian group which is isomorphic to the direct product of and the sandpile group. The order of the latter is the tree number of the graph.