BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T211556Z
UID:Seminar-NESTiD-1142@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Othon Michail:MAILTO:Othon.Michail@liverpool.ac.uk
DTSTART:20211111T160000
DTEND:20211111T170000
SUMMARY:Durham-Liverpool synergy Series
DESCRIPTION:Viktor Zamaraev: Sharp thresholds in random simple temporal graphs\n\nA graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this work, we consider a simple model of random temporal graph, obtained from an Erd?s-Rényi random graph G_{n,p} by considering a random permutation ? of the edges and interpreting the ranks in ? as presence times. \n\nTemporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at \np=logn/n any fixed pair of vertices can a.a.s. reach each other; \nat 2logn/n at least one vertex (and in fact, any fixed vertex) can a.a.s. reach all others; and \nat 3logn/n all the vertices can a.a.s. reach each other, i.e., the graph is temporally connected. \nFurthermore, the graph admits a temporal spanner of size 2n+o(n) as soon as it becomes temporally connected, which is nearly optimal as 2n?4 is a lower bound. This result is significant because temporal graphs do not admit spanners of size O(n) in general (Kempe et al, STOC 2000). In fact, they do not even admit spanners of size o(n^2) (Axiotis et al, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, all non-negligible obstructions, must be statistically insignificant: nearly optimal spanners always exist in random temporal graphs. \n\nAll the above thresholds are sharp. Carrying the study of temporal spanners further, we show that pivotal spanners -- i.e., spanners of size 2n?2 made of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently) -- exist a.a.s. at 4logn/n, this threshold being also sharp. Finally, we show that optimal spanners (of size 2n?4) also exist a.a.s. at p=4logn/n.\n\nThis is a joint work with Arnaud Casteigts (University of Bordeaux), Michael Raskin (Technical University of Munich), Malte Renken (Technical University of Berlin)\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1142
LOCATION:
END:VEVENT
END:VCALENDAR