Lionel Levine, Cornell University

Abstract

In joint work with Matt Farrell, http://arxiv.org/abs/1502.04690 we suggest a measure of "Eulerianness" of a finite directed graph, and define a class of "coEulerian" graphs. These are the strongly connected graphs whose Laplacian lattice is as large as possible. As an application, we address a problem posed by Bjorner, Lovasz, and Shor in 1991. They asked how to tell if a given chip-firing game will be finite or infinite. Bjorner and Lovasz gave a decision procedure in 1992, which takes exponential time in the worst case. We show this can be improved to linear time (!) if the graph is coEulerian. A recent theorem of Nguyen and Wood, confirming a conjecture of Koplewitz, shows that coEulerian graphs are not rare: The directed random graph G(n,p) is coEulerian with limiting probability 1/(zeta(2)*zeta(3)*zeta(4)*...). So (in case you were wondering) about 43.58% of all simple directed graphs are coEulerian.