On Variants of Diffusion
Abstract
This thesis will examine the Chip Firing variant, diffusion, in many of its different
iterations. We will look at a previously studied version, Parallel Diffusion, along
with four new variants: Quantum Parallel Diffusion, Two-One Diffusion, Pay it Backward,
and Sequential Diffusion. The results discussed will center around the topics
of regularity and periodicity.
Chip-firing processes move chips from vertex to vertex in a graph at discrete time
increments. A specific distribution of chips on the vertices of a graph at a specific time
is referred to as a configuration. We will show that most of these processes exhibit
periodic behaviour, meaning that configurations recur as time increases. Also, in
the instance of Pay it Backward, we see that not every variation guarantees periodic
behaviour. It is with Pay it Backward, however, that we discover some of our most
interesting results regarding the regularity of the movement of chips.
Of those variations which exhibit periodic behaviour, we will show examples of
very large periods and very short periods, and we will also count the number of
periodic configurations that exist in some processes. Specifically, we use Long and
Narayanan’s result that every instance of Parallel Diffusion is eventually periodic
with period 1 or 2 to determine the number of non-equivalent configurations that
exist on paths, complete graphs, and star graphs.