Speaker: Lionel Levine, Cornell University
Title: CoEulerian Graphs
Time: 2:30 PM, Monday, September 9, 2019
Place: Malott 206
Abstract: "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
where \zeta is the Riemann zeta function. So (in case you were wondering) about 43.6% of all simple directed graphs are coEulerian.
Back to main seminar page.