Abstracts
for the Seminar

Fall 2014

**Speaker: ** Matthew Farrell, Cornell University

**Title: **The halting problem for chip-firing on finite directed graphs

**Time:** 2:30 PM, Monday, November 17, 2014

**Place:** Malott 206

**Abstract:**
We consider a chip-firing game on finite directed graphs and give
an answer to a question posed by Bjorner, Lovasz, and Shor in 1991:
given an initial configuration of chips, how difficult is it to determine
whether or not it stabilizes? The approach they took involves computing
a period vector p with the property that toppling the vertices
according to p results in the original configuration, and then
checking if it is possible to topple according to p legally (without
any of the vertices ever having negative chips). This approach is
problematic because the entries of p can grow exponentially in
the number of vertices. We make precise a measure of "Eulerianness''
and show that for "anti-Eulerian'' graphs you can do much better,
but show that in general the problem is NP-Hard. This extends the
class of graphs for which the problem is known to be quickly solvable
beyond the case of "nearly'' Eulerian graphs, and gives a negative
answer to the existence of a polynomial time algorithm for solving
the halting problem for general finite directed graphs.