Dispersion processes

DOI10.1002/RSA.20822MaRDI QIDQ4625017zbMATH OpenOpenAlexFDO

Authors Colin Cooper, Andrew McDowell, Tomasz Radzik, Nicolás Rivera, Takeharu Shiraga

Publication date 20 February 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.03389, https://kclpure.kcl.ac.uk/portal/en/publications/dispersion-processes(9fa03e66-1060-4b86-aed3-aa4833624623).html

zbMATH Keywords

random walkrandom processes on graphsdispersion of particles

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Random walks on graphs (05C81)

Abstract: We study a synchronous dispersion process in which $M$ particles are initially 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 dispersion process ends once the particles have all stopped moving, i.e. at the first step at which each vertex is occupied by at most one particle. For the complete graph $K_n$ and star graph $S_n$, we show that for any constant $delta>1$, with high probability, if $Mlen/2(1-delta)$, then the process finishes in $O(logn)$ steps, whereas if $Mgen/2(1+delta)$, then the process needs $e^{Omega(n)}$ steps to complete (if ever). We also show that an analogous lazy variant of the process exhibits the same behaviour but for higher thresholds, allowing faster dispersion of more particles. For paths, trees, grids, hypercubes and Cayley graphs of large enough sizes (in terms of $M$) we give bounds on the time to finish and the maximum distance traveled from the origin as a function of the number of particles $M$.

Recommendations

• Longest distance of a non-uniform dispersion process on the infinite line
• A note on dispersing particles on a line
• Efficient Dispersion of Mobile Agents without Global Knowledge
• Dispersion on trees
• Coalescing random walks and voting on graphs

Cited in

(9)

• scientific article; zbMATH DE number 4062507 (Why is no real title available?)
• Dispersion on the complete graph (extended abstract)
• Dispersion on the complete graph
• A note on dispersing particles on a line
• Quantitative convergence guarantees for the mean-field dispersion process
• Limit laws for critical dispersion on complete graphs
• Longest distance of a non-uniform dispersion process on the infinite line
• Sticky dispersion on the complete graph: a kinetic approach
• Transient dispersion regimes

This page was built for publication: Dispersion processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625017)