Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Food For Thought

Gregg Musiker

UCSD Graduate Student

Chip-firing games

Abstract:

A chip-firing game is a game played by $n$ players where each player is alotted a certain set of neighbors and a certain number of tokens, here called chips. (In math-speak this would be a graph $G=(V,E)$ with $n$ vertices $v \in V$ with nonnegative integer weights, and the edges $e\in E$ determine which vertices are adjacent.) During the course of each round, starting with player $1$, every player whose chip-stack is greater than his/her number of neighbors must give a chip to each of them. If a player's chip-stack is too small, play skips over to the next player. Once everyone has played, player $1$ goes again if possible, and play continues this way. In this talk, we will discuss several mathematical questions that come up from this model: \begin{enumerate} \item For what initial configurations will play eventually stop? \item Does the order of the players matter? \item Which initial configurations will appear again and again? \end{enumerate} We then consider a new game, called the dollar game as defined by N. Biggs, where an additional player, the bank, is added. The bank takes chips from the players as above, but can only give all of his/her neighbors chips if play would stop otherwise. However the bank player is allowed to go into debt and thus can give his/her neighbors chips whenever play would stop. We will discuss how this new game gives rise to a group structure, and applications. If there is time we will discuss the Matrix-Tree Theorem which lies at the nexus between Algebraic Combinatorics and Graph Theory. \vspace{1em} All are welcome. Even if you do not know what a graph is, all will be explained.

October 5, 2006

1:00 PM

AP&M 7321

****************************