Search Results

Documents authored by Makai, Tamás

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}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.114
Canonical Labelling of Random Regular Graphs

Authors: Mikhail Isaev, Tamás Makai, Brendan D. McKay, Paweł Prałat, Jane Tan, and Maksim Zhukovskii

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We prove that whenever d = d(n) → ∞ and n-d → ∞ as n → ∞, then with high probability for any non-trivial initial colouring, the colour refinement algorithm distinguishes all vertices of the random regular graph 𝒢_{n,d}. This, in particular, implies that with high probability 𝒢_{n,d} admits a canonical labelling computable in time O(min{n^ω, nd²+ndlog n}), where ω < 2.372 is the matrix multiplication exponent.
Cite as

Mikhail Isaev, Tamás Makai, Brendan D. McKay, Paweł Prałat, Jane Tan, and Maksim Zhukovskii. Canonical Labelling of Random Regular Graphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 114:1-114:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{isaev_et_al:LIPIcs.ICALP.2026.114,
  author =	{Isaev, Mikhail and Makai, Tam\'{a}s and McKay, Brendan D. and Pra{\l}at, Pawe{\l} and Tan, Jane and Zhukovskii, Maksim},
  title =	{{Canonical Labelling of Random Regular Graphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{114:1--114:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.114},
  URN =		{urn:nbn:de:0030-drops-265039},
  doi =		{10.4230/LIPIcs.ICALP.2026.114},
  annote =	{Keywords: random graphs, regular graphs, colour refinement, canonical labelling, graph isomorphism}
}
Document
DOI: 10.4230/LIPIcs.AofA.2024.26
Limit Laws for Critical Dispersion on Complete Graphs

Authors: Umberto De Ambroggio, Tamás Makai, Konstantinos Panagiotou, and Annika Steibel

Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)

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 a vertex of G. In subsequent time steps, all particles that are located on a vertex inhabited by at least two particles jump 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; we call this (random) time step the dispersion time. In this work we study the case where G is the complete graph on n vertices and the number of particles is M = n/2+α n^{1/2} + o(n^{1/2}), α ∈ ℝ. This choice of M corresponds to the critical window of the process, with respect to the dispersion time. We show that the dispersion time, if rescaled by n^{-1/2}, converges in p-th mean, as n → ∞ and for any p ∈ ℝ, to a continuous and almost surely positive random variable T_α. We find that T_α is the absorption time of a standard logistic branching process, thoroughly investigated by Lambert (2005), and we determine its expectation. In particular, in the middle of the critical window we show that 𝔼[T₀] = π^{3/2}/√7, and furthermore we formulate explicit asymptotics when |α| gets large that quantify the transition into and out of the critical window. We also study the random variable counting the total number of jumps that are performed by the particles until the dispersion time is reached and prove that, if rescaled by nln(n), it converges to 2/7 in probability.
Cite as

Umberto De Ambroggio, Tamás Makai, Konstantinos Panagiotou, and Annika Steibel. Limit Laws for Critical Dispersion on Complete Graphs. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 26:1-26:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{deambroggio_et_al:LIPIcs.AofA.2024.26,
  author =	{De Ambroggio, Umberto and Makai, Tam\'{a}s and Panagiotou, Konstantinos and Steibel, Annika},
  title =	{{Limit Laws for Critical Dispersion on Complete Graphs}},
  booktitle =	{35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)},
  pages =	{26:1--26:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-329-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{302},
  editor =	{Mailler, C\'{e}cile and Wild, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.26},
  URN =		{urn:nbn:de:0030-drops-204617},
  doi =		{10.4230/LIPIcs.AofA.2024.26},
  annote =	{Keywords: Random processes on graphs, diffusion processes, stochastic differential equations, martingale inequalities}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact