Dispersion processes

TY - JOUR

T1 - Dispersion processes

AU - Cooper, Colin

AU - McDowell, Andrew

AU - Radzik, Tomasz

AU - Rivera Aburto, Nicolas

AU - Shiraga, Takeharu

PY - 2018/12

Y1 - 2018/12

N2 - 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 neighbour 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 d > 1, with high probability, if M <= n/2(1 - d), the dispersion process finishes in O(log n) steps, whereas if M >= n/2(1 + d), the process needs e^Omega(n) steps to complete, if ever. A lazy variant of the process exhibits analogous behaviour 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.

AB - 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 neighbour 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 d > 1, with high probability, if M <= n/2(1 - d), the dispersion process finishes in O(log n) steps, whereas if M >= n/2(1 + d), the process needs e^Omega(n) steps to complete, if ever. A lazy variant of the process exhibits analogous behaviour 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.

U2 - 10.1002/rsa.20822

DO - 10.1002/rsa.20822

M3 - Article

SN - 1042-9832

VL - 53

SP - 561

EP - 585

JO - RANDOM STRUCTURES AND ALGORITHMS

JF - RANDOM STRUCTURES AND ALGORITHMS

IS - 4

ER -