Discrete Geometry and Combinatorics Seminar
"Will this procedure be finite or infinite? If finite, how long can it last?" Bjorner, Lovasz, and Shor asked these questions in 1991 about the following procedure: Given a configuration of chips on the vertices of a finite directed graph, choose (however you like) a vertex with at least as many chips as out-neighbors, and send a chip from that vertex to each out-neighbor. Repeat, until there is no such vertex. In joint work with Matt Farrell, we show that the first question above is NP-complete in general. But there is a curious class of graphs, the "coEulerian graphs", for which halting is easy to decide even though it may last for exponentially many steps! A recent theorem of Hoi Nguyen and Melanie Wood 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)... ) where \zeta is the Riemann zeta function. So (in case you were wondering) about 43.6% of all simple directed graphs are coEulerian.