Becker, R, Crescenzi, P, Renken, M, Zamaraev, V 
ORCID: 0000-0001-5755-4141, Casteigts, A, Kodric, B and Raskin, M
(2023)
Giant Components in Random Temporal Graphs.
.
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 far-reaching consequences. Recently, Casteigts et al. [FOCS 2021] proposed a natural temporal analog of the seminal Erdős-Ré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ős-Rényi random graph and interpreting this permutation as an ordering of presence times. Casteigts et al. showed that the well-known single threshold for connectivity in the Erdős-Ré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., non-temporal) 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 n − o(n) nodes. This transition occurs significantly later than in the static setting, where a giant component of size n − o(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ős-Rényi graphs, which could be of general interest in future investigations of these objects.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 05 Oct 2023 10:18 |
| Last Modified: | 05 Oct 2023 11:44 |
| DOI: | 10.4230/LIPIcs.APPROX/RANDOM.2023.29 |
| Open Access URL: | https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.... |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3173436 |
Dimensions
Dimensions
