Sharp Thresholds for Temporal Motifs and Doubling Time in Random Temporal Graphs

In this paper we study two natural models of $\mathit{\text{random}}\mathit{\text{temporal}}$ graphs. In the first, the $\mathit{\text{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 $\mathit{\text{discrete}}$ model, the $l_e$ labels of each edge $e$ are chosen uniformly at random from a set $\{1,2,\dots ,T\}$. In both models we study the existence of $\delta \mathit{\text{-temporal}}\mathit{\text{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 $\mathit{\text{sharp}}\mathit{\text{existence}}\mathit{\text{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 $\mathit{\text{doubling}}\mathit{\text{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 $\mathit{\text{sharp}}\mathit{\text{upper}}\mathit{\text{and}}\mathit{\text{lower}}\mathit{\text{bounds}}$ for the maximum doubling time in the continuous model.