Abstracts for the Seminar
 Discrete Geometry and Combinatorics
 Fall 2019

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

Back to main seminar page.