Vienna Combinatorics Seminar

On the unreasonable effectiveness of vertex sampling in graph theoretic problems

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.

On the number of distinct common ancestors in deterministic and

random trees

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).