Given a configuration of chips on the vertices of a finite directed graph, choose (however you like) a vertex \(v\) with at least as many chips as out-neighbors, and send one chip from \(v\) to each out-neighbor of \(v\). Repeat, until there is no such vertex.
Björner, Lovász, and Shor asked in 1991, "Will this procedure be finite or infinite? If finite, how long can it last?" In joint work with Matt Farrell,
https://arxiv.org/abs/1502.04690, we found a curious class of graphs, the "coEulerian graphs", for which the decision problem ("Will this procedure be finite or infinite?") is easy, even though the procedure may last for exponentially many steps!
A theorem of Hoi Nguyen and Melanie Wood,
https://arxiv.org/abs/1806.00596, 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)\ldots)\), where \(\zeta\) is the Riemann zeta function. So (in case you were wondering) about 43.6% of all simple directed graphs are coEulerian.
Please email Anton Bernshteyn (abernsht ~at~ math.cmu.edu) for a password.
The ACO Seminar (2019–2020)