Discrete Geometry and Combinatorics Seminar

Lionel LevineCornell University
CoEulerian Graphs

Monday, September 9, 2019 - 2:30pm
Malott 206

"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.