Time: 16:15-17:30 (exceptional timing because of the GSA meeting at 17:30)

Location: Mondi 3

Speaker 1:  Pasha Arkhipov (Kolmogorov group)

Title: Maximal k forests with bounded indegrees and their cool properties

Abstract: There are two problems that turn out to be closely related. Let G = (V, E) be a directed graph, multiple edges are allowed. The first problem is to find k edge-disjoint forests of maximal size in G such that each vertex v in V has its total indegree in these forests of at most k. In the second problem, one needs to find a minimal set of new edges that makes G k-connected. We will show how the solution for the second problem can be expressed with the solution of the first problem, improving the best known complexity bound for it.

Speaker 2: Damiano de Gaspari (TU Wien)

Title: Bootstrap Percolation on non-amenable graphs

Abstract: Bootstrap Percolation is a cellular automaton with a very simple description: given an initial configuration in which each vertex of the graph is either occupied or vacant, at each time step vacant vertices become occupied if they have at least a certain number of occupied neighbours. We focus on the case in which the underlying graph is "expanding". In the first part of the talk we discuss some classical questions on the model and relate it to the speaker's own research. In the second part, instead, we present a simple proof which allows us to show key ideas and tools both in probability and in the problem at hand. The presentation is accessible to a general audience.