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.

Example graph with the state variables s(v) indicated
A possible finite firing sequence, with the vertex to be fired in red – the game ends as each vertex has s smaller than its degree

Each vertex has the number of "chips" indicated by its state variable. On each firing, a vertex is selected and one of its chips is transferred to each neighbour (vertex it shares an edge with). The number of chips on each vertex cannot be negative. The game ends when no firing is possible.

Definition

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 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 (on a connected graph).

  • 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.

For finite chip-firing games, the possible orders of firing events can be described by an antimatroid. It follows from the general properties of antimatroids that the number of times each vertex fires, and the eventual stable state, do not depend on the order of firing events.[1]

Dollar games

Some chip-firing games, known as dollar games, interpret the chips as dollars and the vertices as money borrowers and lenders. Two variants of dollar game are prominent in the literature:

Baker and Norine's variant

In this dollar game, negative integer values (representing debt) are assigned to some of the vertices of the finite graph G. A game is called winnable if there exists a state where all the vertices can be made positive.[2] A a graph-theoretic analogue of Riemann–Roch theorem can be used to characterize if a game is winnable or not.[2][3]

Biggs's Variant

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 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.[4][5]

See also

References
  1. Björner, Anders; Lovász, László; Shor, Peter W. (1991). "Chip-firing games on graphs". European Journal of Combinatorics. 12 (4): 283–291. doi:10.1016/S0195-6698(13)80111-4. MR 1120415. Knauer, Kolja (2009). "Chip-firing, antimatroids, and polyhedra". European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009). Electronic Notes in Discrete Mathematics. Vol. 34. pp. 9–13. doi:10.1016/j.endm.2009.07.002. MR 2591410.
  2. Baker, Matthew; Norine, Serguei (2007). "Riemann–Roch and Abel–Jacobi theory on a finite graph". Advances in Mathematics. 215 (2): 766–788. doi:10.1016/j.aim.2007.04.012.
  3. Lamboglia, Sara; Ulirsch, Martin. "From the dollar game to the Riemann-Roch Theorem". Snapshots of Modern Mathematics from Oberwolfach. doi:10.14760/SNAP-2021-001-EN.
  4. Biggs, Norman L. (25 June 1997). "Chip-Firing and the Critical Group of a Graph" (PDF). Journal of Algebraic Combinatorics: 25–45. Retrieved 10 May 2014.
  5. wikidot. "Chip-firing references". Retrieved 19 May 2014.
  • 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.