Limit laws for critical dispersion on complete graphs

Abstract

We consider a synchronous process of particles moving on the vertices of a graph G, introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (Random Structures Algorithms 53 (2018) 561–585). Initially, M particles are placed on a vertex of G. In subsequent time steps, all particles that are located on a vertex inhabited by at least two particles jump independently to uniform random neighbours. The process ends at the first step when no vertex is inhabited by more than one particle; we call this (random) time step the dispersion time. We study the case where G is the complete graph on n vertices and the number of particles is M=n/2+αn+o(n), α∈R. This choice of M corresponds to the critical window of the process, with respect to the dispersion time. We show that the dispersion time, if scaled by 1/n, converges in pth mean, for any p∈R and as n→∞, to a continuous and almost surely positive random variable T(α). We find that T(α) is the absorption time of a standard logistic branching process and we determine its expectation. In particular, in the middle of the critical window E[T(0)]=π3/2/ 7, and furthermore we formulate explicit asymptotics when |α| gets large that quantify the transition into and out of the window. We also study the total number of jumps that are performed by the particles until the dispersion time is reached. We prove that it centers around 27nlnn and that it has variations linear in n, whose distribution we describe explicitly.