Journal of Combinatorics

Volume 10 (2019)

Number 2

Diffusion on graphs is eventually periodic

Pages: 235 – 241

DOI: https://dx.doi.org/10.4310/JOC.2019.v10.n2.a3

Authors

Jason Long (Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, United Kingdom)

Bhargav Narayanan (Department of Mathematics, Rutgers University, Piscataway, New Jersey, U.S.A.)

Abstract

We study a variant of the chip-firing game called diffusion. In diffusion on a graph, each vertex of the graph is initially labelled with an integer interpreted as the number of chips at that vertex, and at each subsequent step, each vertex simultaneously fires one chip to each of its neighbours with fewer chips. Since this firing rule may result in negative labels, diffusion, unlike the parallel chip-firing game, is not obviously periodic. In 2016, Duffy, Lidbetter, Messinger and Nowakowski nevertheless conjectured that diffusion is always eventually periodic, and moreover, that the process eventually has period either $1$ or $2$. Here, we establish this conjecture.

Received 23 November 2017

Published 25 January 2019