[Facets-of-complexity] Invitation to Monday's Lecture & Colloquium Dec.6 !

["I.Brunke" <i.brunke@fu-berlin.de>]

Dear all,

next Monday's Lecture and Colloquium will take place online via Zoom on December 6.

Please find link to Zoom here:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09
No password is required.

You all are cordially invited!

Location:

Online via Zoom.

Monday's Lecture: Arnaud Casteigts (Université de Bordeaux)

Time: Monday, December 6 - 14:15 h

Title: Spanners and connectivity problems in temporal graphs

Abstract:

A graph whose edges only appear at certain points in time is called a temporal graph. 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 talk, I will focus on the concept of a temporal spanner, which is a subgraph of the input temporal graph that preserves temporal connectivity using as few edges (or labels) as possible. In stark contrast with standard graphs, it turns out that linear size spanners, and in fact, even sparse spanners (i.e., spanners with o(n^{^2}) edges) do not always exist in temporal graphs. After presenting basic notions and reviewing these astonishing negative results, I will present some good news as well; namely, sparse spanners always exist in *some* natural classes of temporal graphs. These include the cases when the underlying graph is complete (this talk) or when the labels are chosen at random (subsequent talk). If time permit, I will present two open questions, and discuss some recent attempts at solving them.


Break

Monday's Colloquium: Malte Renken (Technische Universität Berlin)

Time: Monday, December 6 - 16:00 h s.t.

Title: Connectivity Thresholds in Random Temporal Graphs

Abstract:

We consider a simple model of a random temporal graph, obtained by assigning to every edge of an Erdős–Rényi random graph G_n,p a uniformly random presence time in the real interval [0, 1]. We study several connectivity properties of this random temporal graph model and uncover a surprisingly regular sequence of sharp thresholds at which these different levels of connectivity are reached. Finally, we discuss how our results can be transferred to other random temporal graph models. Based on joint work with Arnaud Casteigts, Michael Raskin, and Viktor Zamaraev.

You all are cordially invited!

Virenfrei. www.avast.com