Tel Aviv University
Abstract:
Based on the research experience of the speaker, we will showcase several quite diverse graph theoretic problems, where vertex percolation or more generally vertex sampling play a crucial role, despite their apparent irrelevance to the problem at hand.
ENS Lyon
Abstract:
Consider a rooted, deterministic or random tree, and pick a sequence of independent k-tuples of points in the tree. Each of these k-tuples determines a most recent common ancestor, and we are interested in studying the number of distinct common ancestors that have been selected by the first n random k-tuples. This problem was recently considered by Chapuy, in relation to the computation of the edge-density of the Brownian co-graphon. Chapuy considered the case where k = 2 and where the tree structure is the Brownian continuum random tree (CRT) of Aldous. His methods were combinatorial, and he asked for a more probabilistic proof making the connection to the stochastic processes associated with the CRT. We propose such an approach, based on a reformulation of the problems in terms of urn schemes, which allows to extend considerably the scope of this result, by considering the case of a general k, and a wide family of trees to sample from. Interestingly, depending on the model, a phase transition can occur and yield either random or deterministic limits, depending on the value of k. This is a joint work with Bénédicte Haas (Université Sorbonne Paris-Nord).
17 November 2026
Venue: ISTA, Raiffeisen Hall
15:30 - 16:20
ISTA
A simple exercise appearing in many graph theory courses is that if a graph has minimum degree d, then it contains a cycle of length at least d+1. A substantially more challenging generalization of this is a celebrated theorem of Erdős and Gallai, which states that the same conclusion holds if we only assume that the average degree is d.
Although the Erdős–Gallai theorem has a relatively short proof, I personally find it somewhat mysterious and unenlightening. In this talk, I will discuss a new proof of the Erdős–Gallai theorem, which has the disadvantages of being a lot more complicated and of proving a somewhat weaker statement. However, its advantages are (a) that it sheds more light on why such a statement should be true, and (b) that it can also be used to prove some interesting and surprising generalizations. Along the way, I will discuss a remarkable recent result of Pokrovskiy, which reveals a great deal about the structure of sparse graphs.
Based on joint work with Micha Christoph and Alp Müyesser.
1 December 2026
Venue: University of Vienna, Faculty of Mathemtics, Oskar Morgenstern Platz 1, HS13
16:45 - 18:35
Oxford University
Abstract:
19 January 2027
Venue: University of Vienna, Faculty of Mathemtics, Oskar Morgenstern Platz 1, HS17
15:00 - 17:00
TU Wien
Abstract: