DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2026.25

The Dispersion Process Has the Same Phase Transition on Almost Every Graph

Authors: Julius Hallmann, Kostas Lakis, and Tamás Makai

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract

The Dispersion process was introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (2018), in which a number of particles are initially placed on a given vertex of a graph and update their positions according to the following dynamics. In each round, the particles which are not alone on a vertex (called unhappy) simultaneously move to a uniformly random neighbor. In contrast, the rest of the particles (called happy) stay put. The process terminates once every particle is happy. When the process runs on the complete graph, they showed that there is a phase transition with respect to the running time when the number of particles reaches n/2. Below this threshold the running time is logarithmic, while above the threshold it is exponential. We show that the same behavior holds for the binomial random graph G(n, 1/2) with high probability. The main difference to the complete graph is that the number of happy particles in the neighborhood of a vertex can vary significantly from vertex to vertex, resulting in differing local behaviors. Fortunately the number of such vertices is limited and thus they only have a negligible effect on the running time of the process.

Cite as

Julius Hallmann, Kostas Lakis, and Tamás Makai. The Dispersion Process Has the Same Phase Transition on Almost Every Graph. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 25:1-25:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hallmann_et_al:LIPIcs.AofA.2026.25,
  author =	{Hallmann, Julius and Lakis, Kostas and Makai, Tam\'{a}s},
  title =	{{The Dispersion Process Has the Same Phase Transition on Almost Every Graph}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{25:1--25:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.25},
  URN =		{urn:nbn:de:0030-drops-262960},
  doi =		{10.4230/LIPIcs.AofA.2026.25},
  annote =	{Keywords: Dispersion process, Random Graphs, Drift analysis}
}

Search Results

Documents authored by Hallmann, Julius

The Dispersion Process Has the Same Phase Transition on Almost Every Graph

Abstract

Cite as

Thanks for your feedback!

Could not send message