EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Dispersion on the Complete Graph

Umberto De Ambroggio, Tamás Makai, Konstantinos Panagiotou

Random Structures & Algorithms · 2025-01 · 66 (1)

DOI: 10.1002/rsa.21266 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 11.11.2024. Verfasst von Umberto De Ambroggio und 2 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 10 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider a synchronous process of particles moving on the vertices of a graph , introduced by Cooper et al. Initially, particles are placed on a vertex of . At the beginning of each time step, for every vertex inhabited by at least two particles, each of these particles moves independently to a neighbor 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 vertices, then there is a phase transition when the number of particles . They showed that if for some fixed , then the process finishes in a logarithmic number of steps, while if , an exponential number of steps are required with high probability. Here we provide a thorough asymptotic analysis of the dispersion time around criticality, where , and describe the transition from logarithmic to exponential time. As a consequence of our results we establish, for example, that the dispersion time is in probability and in expectation in when , and provide qualitative bounds for its tail behavior.

Förderung

  • European Research Council

Zitieren

APA

Ambroggio, U. D., Makai, T., & Panagiotou, K. (2025). Dispersion on the Complete Graph. Random Structures & Algorithms, 66(1). https://doi.org/10.1002/rsa.21266

Vancouver

Ambroggio UD, Makai T, Panagiotou K. Dispersion on the Complete Graph. Random Structures & Algorithms. 2025;66(1). doi:10.1002/rsa.21266

BibTeX
@article{Ambroggio2025,
  author = {Ambroggio, Umberto De and Makai, Tamás and Panagiotou, Konstantinos},
  title = {Dispersion on the Complete Graph},
  journal = {Random Structures & Algorithms},
  year = {2025},
  volume = {66},
  number = {1},
  doi = {10.1002/rsa.21266}
}
Infokarte | EUVIMED

Artikeldaten derzeit nicht verfügbar.

Recherche