Paths and cliques in random temporal graphs

Motivated by modeling time-dependent processes on networks like social interactions and infection spread, we consider a version of the classical Erdős–Rényi random graph G(n,p) where each edge has a distinct random timestamp, and connectivity is constrained to sequences of edges with increasing timestamps. We present results on the lengths of the shortest and longest increasing paths, as well as the size of the largest temporal clique that exhibits a remarkable phase transition. Time permitting, we introduce a novel random tree model motivated by random temporal graphs.

This talk is based on joint work with Nicolas Broutin, Nina Kamčev, Caelan Atamanchuk, and Luc Devroye.