Sharing tea on a graph

Abstract

Motivated by the analysis of consensus formation in the Deffuant model for social interaction, we consider the following procedure on a graph $G$. Initially, there is one unit of tea at a fixed vertex $r\in V(G)$, and all other vertices have no tea. At any time in the procedure, we can choose a connected subset of vertices $T$ and equalize the amount of tea among vertices in $T$. We prove that if $x\in V(G)$ is at distance $d$ from $r$, then $x$ will have at most $\frac{1}{d+1}$ units of tea during any step of the procedure. This bound is best possible and answers a question of Gantert. We also consider arbitrary initial weight distributions. For every finite graph $G$ and $w\in {\mathbb{R}}_{\ge 0}^{V(G)}$, we prove that the set of weight distributions reachable from $w$ is a compact subset of ${\mathbb{R}}_{\ge 0}^{V(G)}$.

18 pages, 2 figures