11:00
12:00

Michael Raskin (LaBRI)

Title: Giant Components in Random Temporal Graphs

Abstract:

A temporal graph is a graph whose edges appear only at certain points in time. Recently, a natural temporal analog of the Erdős-Rényi random graph model has been introduced. The proposed model is obtained by randomly permuting the edges of an Erdős-Rényi random graph and interpreting this permutation as an ordering of presence times. It was shown that the connectivity threshold in the Erdős-Rényi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting.

In the present paper, we identify a sharp threshold for the emergence of a giant temporally connected component. We show that at p = log n/n the size of the largest temporally connected component increases from o(n) to n-o(n). This threshold holds for both open and closed connected components, i.e. components that allow, respectively forbid, their connecting paths to use external nodes.

https://algodist.labri.fr/index.php/Main/GT

LaBRI salle 178 - lien visio https://webconf.u-bordeaux.fr/b/arn-4tr-7gp