Dispersion on the Complete Graph

EUROCOMB’23

Umberto De Ambroggio Tamas Makai Konstantinos Panagiotou

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-046

PDF
Abstract
We consider a synchronous process of particles moving on the vertices of a graph $G$, introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (2018). Initially, $M$ particles are placed on one vertex of $G$. At the beginning of each time step, for every vertex inhabited by at least two particles, each of these particles moves independently to a neighbour chosen uniformly at random. The process ends at the first step when no vertex is inhabited by more than 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 the number of particles $M = n/2$. They showed that if $M<(1-\varepsilon)n/2$ for some fixed $\varepsilon>0$, then the process finishes in a logarithmic number of steps, while if $M>(1+\varepsilon)n/2$, an exponential number of steps are required with high probability. In this paper we provide a thorough analysis of the distribution of the dispersion time in the barely critical regime, where $\varepsilon =o(1)$, and describe the fine details of the transition between logarithmic and exponential time. As a consequence of our results we establish, for example, that the dispersion time is in probability and in expectation $\Theta(n^{1/2})$ when $|\varepsilon| = O(n^{-1/2})$, and provide qualitative bounds for its tail behavior.

Pages:
336–342
References

C. Cooper, A. McDowell, T. Radzik, N. Rivera, and T. Shiraga. Dispersion processes. Random Structures Algorithms, 53(4):561-585, 2018.
https://doi.org/10.1002/rsa.20822

P. Diaconis and W. Fulton. A growth model, a game, an algebra, Lagrange inversion, and characteristic classes. Rend. Sem. Mat. Univ. Politec. Torino, 49(1):95-119, 1991.

A. Frieze and W. Pegden. A note on dispersing particles on a line. Random Structures Algorithms, 53(4):586-591, 2018.
https://doi.org/10.1002/rsa.20821

G. F. Lawler, M. Bramson, and D. Gri#eath. Internal di#usion limited aggregation. Ann. Probab., 20(4):2117-2140, 1992.
https://doi.org/10.1214/aop/1176989542

J. Lengler. Drift analysis. In B. Doerr and F. Neumann, editors, Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, Nat. Comput. Ser., pages 89-131. Springer, 2020.
https://doi.org/10.1007/978-3-030-29414-4_2

J. Lengler and A. Steger. Drift analysis and evolutionary algorithms revisited. Combin. Probab. Comput., 27(4):643-666, 2018.
https://doi.org/10.1017/S0963548318000275

R. Lyons and Y. Peres. Probability on trees and networks, volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, New York, 2016.
https://doi.org/10.1017/9781316672815

Y. Shang. Longest distance of a non-uniform dispersion process on the in#nite line. Inform. Process. Lett., 164:106008, 5, 2020.
https://doi.org/10.1016/j.ipl.2020.106008

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Umberto De Ambroggio, Tamas Makai, Konstantinos Panagiotou

PDF