Chip-firing game

Let the finite graph G be connected and loopless, with vertices V = {1, 2, . . . , n}. Let deg(v) be the degree of a vertex, and e(v,w) 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(v), 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(w) ≥ deg(w). The vertex w is fired, moving one chip from w along each incident edge to a neighbouring vertex, producing a new configuration ${\displaystyle s'}$ defined by:

${\displaystyle s'(w)=s(w)-\deg(w)}$

and for v ≠ w,

${\displaystyle s'(v)=s(v)+e(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.

• If the number of chips is less than the number of edges, the game is always finite, reaching a stable state.
• If each vertex has fewer chips than its degree, the game is finite.

• If the number of chips is at least the number of edges, the game can be infinite, never reaching a stable state, for an appropriately chosen initial configuration.
• If the number of chips is more than twice the number of edges minus the number of vertices, the game is always infinite.

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(q) < 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 (i.e. for which only q can fire) and recurrent for this game can be given the structure of an abelian group which is isomorphic to the direct product of ${\displaystyle \mathbb {Z} }$ and the sandpile group (also referred to as Jacobian group or critical group). The order of the latter is the tree number of the graph.[1][2]

• Abelian sandpile model
• The Mathematics of Chip-Firing

• A. Björner, L. Lovász, P. W. Shor: Chip-firing games on graphs. European Journal of Combinatorics archive, Volume 12 Issue 4, July 1991, Pages 283–291 doi:10.1016/S0195-6698(13)80111-4 PDF
• A. Björner, L. Lovász: Chip-Firing Games on Directed Graphs. Journal of Algebraic Combinatorics, December 1992, Volume 1, Issue 4, pp 305–328 doi:10.1023/A:1022467132614

• MIT Course 18.312: Algebraic Combinatorics
• Weisz Ágoston: A koronglövő játék. Szakdolgozat, ELTE TTK Bsc, 2014
• Chip firing survey on Egerváry Research Group
• Games built on chip-firing (2010)
• The Dollar Game - Numberphile video