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.