PC Seminar: Temporal connectivity in random graphs

Abstract: A temporal random graph is a random graph in which all edges are endowed with a uniformly random time-stamp, representing the time of interaction between vertices. In such graphs, paths with increasing time stamps indicate the propagation of information. In this talk we will first introduce temporal graphs and give a short overview of previous work. We will then introduce temporal random geometric graphs, which are temporal graphs with an underlying random geometric graph. For such graphs, we determine a threshold for the existence of monotone increasing paths between all pairs of vertices in temporal random geometric graphs. The results reveal that temporal connectivity appears at a significantly larger edge density than simple connectivity of the underlying random geometric graph. This is in contrast with Erdős-Rényi random graphs in which the thresholds for temporal connectivity and simple connectivity are of the same order of magnitude. This talk is based on joint work with Anna Brandenberger, Serte Donderwinkel, Gábor Lugosi and Rivka Mitchell.

This is a seminar in our seminar series on Probability and Combinatorics (PC).