**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 order in which topplings occur in a given turn does not matter.
- The game must end by at most $1+\sum_{v}(d(v)-1)$ turns, as no stable position has this many tokens. (The total is $2|E(G)|-|V(G)|+1$.)
- The game must last at least $|E(G)|$ turns, and in any graph it is possible for the game to end after $|E(G)|$ turns.

**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?