Giant Components in Random Temporal Graphs
SIAM Journal on Discrete Mathematics · 30.06.2026 · 40 (2) · 449-485
DOI: 10.1137/24m1673206 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 01.04.2026. Verfasst von Ruben Becker und 6 weiteren Autor:innen. Die Arbeit nennt 41 Literaturangaben. Gefördert von: Agence Nationale de la Recherche, Deutsche Forschungsgemeinschaft, European Research Council.
Abstract (Originalsprache)
A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erdős–Rényi random graph model. The proposed model is obtained by randomly permuting the edges of an Erdős–Rényi random graph and interpreting this permutation as an ordering of presence times. It was shown that the connectivity threshold in the Erdős–Rényi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting. In the present paper, we identify a sharp threshold for the emergence of a giant temporally connected component. We show that at [Formula: see text] the size of the largest temporally connected component increases from [Formula: see text] to [Formula: see text]. This threshold holds for both open and closed connected components, i.e., components that allow (respectively, forbid) their connecting paths to use external nodes.
Förderung
- Agence Nationale de la Recherche
- Deutsche Forschungsgemeinschaft
- European Research Council
Zitieren
APA
Becker, R., Casteigts, A., Crescenzi, P., Kodric, B., Raskin, M., Renken, M., & Zamaraev, V. (2026). Giant Components in Random Temporal Graphs. SIAM Journal on Discrete Mathematics, 40(2), 449-485. https://doi.org/10.1137/24m1673206
Vancouver
Becker R, Casteigts A, Crescenzi P, Kodric B, Raskin M, Renken M, et al. Giant Components in Random Temporal Graphs. SIAM Journal on Discrete Mathematics. 2026;40(2):449-485. doi:10.1137/24m1673206
BibTeX
@article{Becker2026,
author = {Becker, Ruben and Casteigts, Arnaud and Crescenzi, Pierluigi and Kodric, Bojana and Raskin, Michael and Renken, Malte and Zamaraev, Viktor},
title = {Giant Components in Random Temporal Graphs},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {2},
pages = {449--485},
doi = {10.1137/24m1673206}
}
EUVIMED