The Dispersion Process for Particles on Graphs

In this thesis, we study a process called Dispersion, in which M particles are dispersed among the vertices of a graph G. All particles initially occupy a single vertex called the origin vertex. At each discrete time step, all particles which share a vertex with at least one other, move to a randomly (though not necessarily uniformly) chosen neighbor of the currently occupied vertex. The process ends when each vertex is occupied by at most one particle. We will explore various aspects of the Dispersion process. One of these is the expected time to completion, E[TDisp] for 3 particles on an n-cycle. Another point of analysis will be the differences in the behavior of particles on even-length cycles vs. odd-length cycles