2026/02/02 by Henry Austin, George B. Mertzios, Paul G. Spirakis · 1 voice
Computer Science · Mathematics · #cs.DM #math.PR
paper · pdf · doi:10.48550/arxiv.2602.01847
arxiv published 2026/02/02 · arxiv updated 2026/06/26
In this paper we study two natural models of random temporal graphs. In the first, the continuous model, each edge e is assigned le labels, each drawn uniformly at random from (0,1], where the numbers le are independent random variables following the same discrete probability distribution. In the second, the discrete model, the le labels of each edge e are chosen uniformly at random from a set \1,2,…,T\. In both models we study the existence of δ-temporal motifs. Here a δ-temporal motif consists of a pair (H,P), where H is a fixed static graph and P is a partial order over its edges. A temporal graph G=(G,λ) contains (H,P) as a δ-temporal motif if G has a simple temporal subgraph on the edges of H whose time labels are ordered according to P, and whose life duration is at most δ. We prove sharp existence thresholds for all δ-temporal motifs, and we identify a qualitatively different behavior from the analogous static thresholds in Erdos-Renyi random graphs. Applying the same techniques, we then characterize the growth of the largest δ-temporal clique in the continuous variant of our random temporal graphs model. Finally, we consider the doubling time of the reachability ball centered on a small set of vertices of the random temporal graph as a natural proxy for temporal expansion. We prove sharp upper and lower bounds for the maximum doubling time in the continuous model.