# Chip-firing

## Introduction

Chip-firing is a solitary game on a directed graph, defined by Björner, Lovász and Shor [1], [2]. In this game we consider a digraph $G$ with a pile of chips on each of its nodes. A position of the game, called a chip-distribution is described by a vector $x \in \mathbb{Z}^V$, where $x(v)$ denotes the number of chips on vertex $v \in V$. The basic move of the game is firing a vertex. It means that this vertex passes a chip to its neighbors along each outgoing edge, and so its number of chips decreases by its outdegree. In other words, firing a vertex $v$ means taking the new chip-distribution $x - L_G \mathbf{1}_v$ instead of $x$; where $L_G$ denotes the Laplacian matrix of $G$.

The firing of a vertex $v \in V$ is legal with respect to a distribution $x$, if $v$ has a nonnegative amount of chips after the firing. A legal game is a sequence of distributions in which every distribution is obtained from the previous one by a legal firing.

Björner, Lovász and Shor proved the Abelian property of the chip-firing game [1]. The Abelian sandpile model is closely related to chip-firing games.

## Halting problem

Let us call a chip-distribution $x$ terminating, if every legal chip-firing game played starting from $x$ terminates, and call it non-terminating, if every legal chip-firing game played starting from $x$ can be continued indefinitely. According to the Abelian property of the chip-firing game, a chip-distribution is either terminating or non-terminating.

While in the case of simple undirected graphs, a terminating chip-firing game cannot last for more than $O(n^4)$ firings [3]; for digraphs and multigraphs, the number of firings in a terminating chip-firing game is not necessarily polynomial. Therefore, it is a natural question whether there exists a polynomial algorithm deciding that a chip-distribution $x$ is terminating or not. This is called the chip-firing halting problem.

 Eulerian Digraph General Directed Graph Simple graph in P [2] Conjecture: NP-hard Multigraph Conjecture: P [4] NP-complete[5]

## Reachability problem

The chip-firing reachability problem is the following: Given two chip-distributions $x$ and $y$, decide whether there exists a legal game transforming $x$ to $y$. If $y$ is reachable from $x$ by a legal game, we denote it by $x\leadsto y$.

While the reachability problem is known to be in P for Eulerian digraphs [2],[4], its complexity is open for non-Eulerian digraphs.

The chip-firing reachability problem is a special case of the reachability problem for integral vector addition systems.

 Eulerian Digraph General Directed Graph Simple graph in P [2] Conjecture: co-NP-hard Multigraph in P [4] Conjecture: co-NP-hard

## Graph divisor theory

In 2007, Baker and Norine proved a graph-theoretic analogue of the classical Riemann-Roch theorem for algebraic curves [6]. This result inspired much research about Riemann-Roch theorems on tropical curves, lattices and directed graphs, and gave rise to a new field usually called as graph divisor theory. As pointed out already in [6], graph divisor theory has a strong connection to chip-firing games.

Some important notions of graph divisor theory are: Linear equivalence of graph divisors, Picard group, Rank of graph divisors, Divisorial gonality of a graph, Reduced graph divisors.

Combinatorial open problems include finding Upper bound on the divisorial gonality of a graph, Complexity of computing a v-reduced divisor in multigraphs.

## Rotor-routing

Rotor routing is played on a ribbon digraph. A ribbon digraph is a digraph, where for each vertex, the out-edges from that vertex have a fixed cyclic order. A rotor-configuration is a mapping, that assigns an outgoing edge (the rotor edge) to each vertex. A chip-and-rotor configuration is a chip-distribution together with a rotor-configuration.

The rotor-routing game proceeds as follows: A vertex can be routed if it has a positive number of chips. If a vertex is routed, the rotor edge of the vertex is augmented to the next edge in the cyclic order, and a chip is taken from the vertex, and is placed on the head of the new rotor edge.

Holroyd et. al [7] defined a group action of the picard group on the set of spanning in-arborescences of a graph with the help of rotor-routing. The computation of this group action is open.

## References

1. A. Björner, L. Lovász, P. Shor, Chip-firing games on graphs, Eur. J. Comb. (1991) DOI link, Author link
2. A. Björner, L. Lovász, Chip-firing games on directed graphs, J. Algebraic Comb. (1992) DOI link, Author link
3. G. Tardos, Polynomial bound for a chip firing game on graphs, SIAM J. Discret. Math. (1988) DOI link,
4. B. Hujter, V. Kiss, L. Tóthmérész, On the complexity of the chip-firing reachability problem, EGRES Technical Report
5. M. Farrell, L. Levine, Coeulerian graphs, Proc. AMS (2016) DOI link, ArXiv link
6. M. Baker, S. Norine, Riemann--Roch and Abel--Jacobi theory on a finite graph, Advances in Mathematics (2007) DOI link, ArXiv Link
7. A. E. Holroyd, L. Levine, K. Mészáros, Y. Peres, J. Propp, D. B. Wilson, Chip-Firing and Rotor-Routing on Directed Graphs, Progress in Probability (2008) DOI link, Author Link