View PDF HTML (experimental)

Abstract:In this paper we study two natural models of random temporal graphs. In the first, the continuous model, each edge $e$ is assigned $l_e$ labels, each drawn uniformly at random from $(0,1]$, where the numbers $l_e$ are independent random variables following the same discrete probability distribution. In the second, the discrete model, the $l_e$ labels of each edge $e$ are chosen uniformly at random from a set $\{1,2,\ldots,T\}$. In both models we study the existence of $\delta$-temporal motifs. Here a $\delta$-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 $\mathcal{G}=(G,\lambda)$ contains $(H,P)$ as a $\delta$-temporal motif if $\mathcal{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 $\delta$. We prove sharp existence thresholds for all $\delta$-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 $\delta$-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.

Submission history

From: Henry Austin [view email]
[v1] Mon, 2 Feb 2026 09:19:55 UTC (250 KB)
[v2] Wed, 11 Feb 2026 09:54:21 UTC (253 KB)
[v3] Fri, 26 Jun 2026 10:28:10 UTC (252 KB)