Sharing Beer on a Graph

 

Consider the following procedure on a graph G. Initially, there is 1 unit of beer at a fixed vertex r of G and all other vertices have no beer. At any time in the procedure, we can choose an edge uv of G and equalize the amount of beer between u and v. We prove that for every vertex x of G, the amount of beer at x is always at most 1/(d+1), where d is the distance from x to r. This bound is best possible and answers a question of Nina Gantert. This problem is motivated by the analysis of consensus formation in the Deffuant model for social interaction, which I will also briefly discuss. 

This is joint work with Kevin Hendey, Hao Huang, Tony Huynh, Bojan Mohar, Sang-il Oum, Ningyuan Yang, Wei-Hsuan Yu, and Xuding Zhu.