Paths in random temporal graphs

Random temporal graphs are a version of the classical Erdős-Rényi random graph $G(n,p)$ where additionally, each edge has a distinct random time stamp, and connectivity is constrained to sequences of edges with increasing time stamps. We are interested in the asymptotics for the distances in such graphs, mostly in the regime of interest where the average degree $np$ is of order $\log n$ ('near' the phase transition).

More specifically, we will discuss the asymptotic lengths of increasing paths: the lengths of the shortest and longest paths between typical vertices, as well as the maxima between any two vertices; this also covers the (temporal) diameter. In the regime $np \gg \log n$, longest increasing paths were studied by Angel, Ferber, Sudakov and Tassion.

The talk contains joint work with Nicolas Broutin and Gábor Lugosi.