Games built on chip-firing (2010)

Originator: Greg Puleo    (presented by Ben Reiniger - REGS 2011)

Definition: A game is played on a connected graph $G$ by two players who alternate turns. A turn consists of two phases. First, the player places a token on any vertex in the graph. Then, if any vertex has at least as many tokens as its degree, it topples, meaning that it gives away one token to each of its neighbors. This second phase repeats as long as any vertex has at least as many tokens as its degree. When the toppling phase continues forever, the last player who moved is the winner.

Background: Puleo introduced this game during study of the game of a Chaos presented in REGS 2010. Chaos was introduced by Joel Lewis [L] based on the sandpile model in physics. The toppling phase is an instance of the chip-firing game introduced in [BLS]. In the chip-firing game, each vertex starts with some pile of tokens, and tokens move by toppling vertices having at least as many tokens as their degree. The following facts are easily extracted from results on the chip-firing game (recall that only connected graphs are considered):

The upper and lower bounds on the length of the game agree for trees, so on a tree the winner is completely determined by parity of the number of edges.

Conjecture 1: Player 1 wins on any complete graph.

Comments: REGS students have proved this when the number of vertices is odd. The conjecture has been checked computationally for small even values. In these examples, if the second player tries to make the game last as long as possible, then the game lasts $n^2-3n+3$ moves. The winning configurations near the end are fairly well-understood, but a proof has not yet been found that player 1 can force a favorable configuration. Meanwhile, the bounds on the number of turns suggest another game.

Definition: The toppling game is played by Max and Min on a connected graph $G$. Moves are exactly as above, but the objectives are different. Max wants the game to last as many moves as possible. Min wants the infinite topple to occur as soon as possible.

Question 2: What is the toppling number for $K_n$ or for other graphs of interest? When can the value equal the lower bound $|E(G)|$ or the upper bound $2|E(G)|-|V(G)|+1$?

Question 3: Cranston showed that the values of the Max-start and Min-start games differ by at most $1$ on any graph. He conjectures that they are equal only on trees.

Comments: As noted above, the upper and lower bounds for trees are the same, so the moves don't matter; the game always ends in exactly $n-1$ moves on an $n$-vertex tree. On an $n$-cycle, the answer may be $n$ or $n+1$; when $n$ is odd the answer is $n+1$ for Max start and $n$ for Min start, but when $n$ is even the answer is $n$ for Max start and $n+1$ for Min start.

References:
[BLS] A. Björner, L. Lovász and P.W. Shor. Chip-firing games on graphs. European J. Combin. 12 (1991), pp. 283-291.
[L] J.B. Lewis. Who wins this two-player game based on the sandpile model?