Séminaire du 18 octobre 2010, 14h00: Nicolas
Broutin, Équipe-projet Algorithms, INRIA
Paris-Rocquencourt.
Cutting down trees with a Markov chainsaw
Suppose you're given a tree and a chainsaw. You cut edges at random,
each time
keeping the portion of the tree containing the root. How many times is
it necessary to
cut an edge in order for the tree to be reduced to the root? We are
interested in studying this process when the initial tree is random,
say a uniform random labelled tree for instance.
We will give a bijective proof of the asymptotic distribution of the
number of cuts, hence short-cutting the current proofs of this
result. The road to explaining the bijection and the main results is a
great opportunity introduce many beautiful combinatorial processes on
trees and lattice paths and the continuous counterpart for continuum
random trees (CRT) and Brownian excursions. In particular, we will
talk about the Markov chain sampling of random trees, the birthday
paradox, the stick-breacking construction of the CRT, forest
fragmentation processes associated to the additive coalescent, hashing
with linear probing, and Poisson logging of the continuum random
tree.
Virginie Collette
Last modified: Mon Sep 20 14:24:06 CEST 2010