Abstract
A temporal graph is a graph whose edges appear only at certain points in time. In these graphs, reachability among nodes relies on paths that traverse edges in chronological order (temporal paths). Unlike standard paths, temporal paths may not be composable, thus the reachability relation is not transitive and connected components (i.e., sets of pairwise temporally connected nodes) do not form equivalence classes, a fact with farreaching consequences.
Recently, Casteigts et al. [FOCS 2021] proposed a natural temporal analog of the seminal ErdősRényi random graph model, based on the same parameters n and p. The proposed model is obtained by randomly permuting the edges of an ErdősRényi random graph and interpreting this permutation as an ordering of presence times. Casteigts et al. showed that the wellknown single threshold for connectivity in the ErdősRényi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting.
The second most basic phenomenon studied by Erdős and Rényi in static (i.e., nontemporal) random graphs is the emergence of a giant connected component. However, the existence of a similar phase transition in the temporal model was left open until now. In this paper, we settle this question. We identify a sharp threshold at p = log n/n, where the size of the largest temporally connected component increases from o(n) to no(n) nodes. This transition occurs significantly later than in the static setting, where a giant component of size no(n) already exists for any p ∈ ω(1/n) (i.e., as soon as p is larger than a constant fraction of n). Interestingly, the threshold that we obtain holds for both open and closed connected components, i.e., components that allow, respectively forbid, their connecting paths to use external nodes  a distinction arising from the absence of transitivity.
We achieve these results by strengthening the tools from Casteigts et al. and developing new techniques that provide means to decouple dependencies between past and future events in temporal ErdősRényi graphs, which could be of general interest in future investigations of these objects.
BibTeX  Entry
@InProceedings{becker_et_al:LIPIcs.APPROX/RANDOM.2023.29,
author = {Becker, Ruben and Casteigts, Arnaud and Crescenzi, Pierluigi and Kodric, Bojana and Renken, Malte and Raskin, Michael and Zamaraev, Viktor},
title = {{Giant Components in Random Temporal Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {29:129:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772969},
ISSN = {18688969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18854},
URN = {urn:nbn:de:0030drops188542},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.29},
annote = {Keywords: random temporal graph, Erd\H{o}s–R\'{e}nyi random graph, sharp threshold, temporal connectivity, temporal connected component, edgeordered graph}
}
Keywords: 

random temporal graph, Erdős–Rényi random graph, sharp threshold, temporal connectivity, temporal connected component, edgeordered graph 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) 
Issue Date: 

2023 
Date of publication: 

04.09.2023 