Dispersion on the Complete Graph
share
We consider a synchronous process of particles moving on the vertices of a graph G, introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (2018). Initially, M particles are placed on a vertex of G. At the beginning of each time step, for every vertex inhabited by at least two particles, each of these particles moves independently to a neighbour chosen uniformly at random. The process ends at the first step when no vertex is inhabited by more than one particle. Cooper et al. showed that when the underlying graph is the complete graph on n vertices, then there is a phase transition when the number of particles M = n/2. They showed that if M<(1-ε)n/2 for some fixed ε>0, then the process finishes in a logarithmic number of steps, while if M>(1+ε)n/2, an exponential number of steps are required with high probability. In this paper we provide a thorough analysis of the dispersion time around criticality, where ε = o(1), and describe the fine details of the transition between logarithmic and exponential time. As a consequence of our results we establish, for example, that the dispersion time is in probability and in expectation Θ(n^1/2) when |ε| = O(n^-1/2), and provide qualitative bounds for its tail behavior.
READ FULL TEXT