Cooper, Colin; Mcdowell, Andrew; Radzik, Tomasz; Rivera, Nicolás; Shiraga, Takeharu Dispersion processes. (English) Zbl 1405.05170 Random Struct. Algorithms 53, No. 4, 561-585 (2018). Summary: We study a synchronous process called dispersion. Initially \(M\) particles are placed at a distinguished origin vertex of a graph \(G\). At each time step, at each vertex \(v\) occupied by more than one particle at the beginning of this step, each of these particles moves to a neighbor of \(v\) chosen independently and uniformly at random. The process ends at the first step when no vertex is occupied by more than one particle. For the complete graph \(K_n\), for any constant \(\delta>1\), with high probability, if \(M\leq n/2(1-\delta)\), the dispersion process finishes in \(O(\log n)\) steps, whereas if \(M\geq n/2(1+\delta)\), the process needs \(e^{\Omega(n)}\) steps to complete, if ever. A lazy variant of the process exhibits analogous behavior but at a higher threshold, thus allowing faster dispersion of more particles. For paths, trees, grids, hypercubes, and abelian Cayley graphs of large enough size, we give bounds on the time to finish and the maximum distance traveled from the origin as a function of \(M\). Cited in 1 ReviewCited in 1 Document MSC: 05C81 Random walks on graphs 05C80 Random graphs (graph-theoretic aspects) 05C85 Graph algorithms (graph-theoretic aspects) 05C12 Distance in graphs Keywords:random processes on graphs; dispersion of particles; random walk PDFBibTeX XMLCite \textit{C. Cooper} et al., Random Struct. Algorithms 53, No. 4, 561--585 (2018; Zbl 1405.05170) Full Text: DOI arXiv Link