Dispersion on the Complete Graph
We consider a synchronous process of particles moving on the vertices of a graph, introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (2018). Initially, M particles are placed on one vertex of the underlying graph. At the beginning of each time step, every particle located on a vertex containing two or more particles jumps independently to a neighbour chosen uniformly at random (thus performing a simple random walk on the graph). The process ends at the first time step in which every vertex is inhabited by at most 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 M passes n/2. Specifically, they showed that if M is strictly smaller than n/2, then the process finishes in a logarithmic number of steps, while if M is strictly larger than n/2, then the process needs an exponential number of steps to terminate. In this talk we analyse the dispersion time around the critical point M=n/2 and describe the details of the transition between logarithmic and exponential time. As a consequence of our results we establish, for example, that the dispersion time is of order n^{1/2} when M is asymptotically n/2, and provide some bounds for its tail behaviour.
Area: CS10 - Random walks and branching processes (Fabio Zucca)
Keywords: Random walk, branching process, analysis of algorithms
Please Login in order to download this file