Universität Duisburg-Essen
Fakultät für Mathematik, Campus Essen
Arbeitsgruppe Wahrscheinlichkeitstheorie

Wolfgang Löhr

# Random Trees

Time and Room: Thursday, 10:00h - 11:45h in WSC-S-U-3.03

Content of the Lecture:
• Discrete random trees
• Uniform ordered/unordered labelled/unlabelled trees
• Galton-Watson trees
• Search trees
• Continuum random trees
• R-trees
• Trees under excursions
• The Brownian continuum random tree (CRT)
• Convergence of trees
• Gromov-Hausdorff convergence
• Gromov-weak convergence
Discrete trees are graph-theoretic trees (graphs with no loops), possibly with additional structure such as an order, a labeling of the nodes/leaves, or weights (representing distances) on the edges. Prominent examples for random discrete trees are Galton-Watson trees (the simplest population model) and random search trees (which play an important rôle in the analysis of algorithms and data structures).
In the lecture, we will mainly be interested in the convergence of large discrete trees to continuous objects, as their size tends to infinity. There are different ways to construct the limiting continuum random trees, for example as (consistent) family of distributions of finite sub-trees, as trees under (random) excursions, or as random metric spaces with certain properties, called R-trees or real trees. These constructions, and different notions of convergence of trees will be discussed.

Prerequisites:
The course is offered in the Master program in Mathematics. It addresses Master students who (want to) specialise in probability theory, as well as PHD-students. Knowledge of the following lectures is required:
• Analysis I-III
• Probability Theory I+II
The course will be taught in English, unless all participants prefer German.

Block Seminar:
The course will be followed by a block seminar in the subsequent semester break. There, students can present a paper related to the theory and obtain 6 ECTS credit points.

Literature:
• Michael Drmota: Random Trees, An Interplay between Combinatorics and Probability. Springer, 2009
• Steve N. Evans: Probability and Real Trees. École d'Été de Probabilités de Saint-Flour XXXV, 2005
Free preprint is available here
• Ian Chiswell: Introduction to Lambda-Trees. World Scientific, 2001
• Andreas Greven, Peter Pfaffelhuber, Anita Winter: Convergence in distribution of random metric measure spaces: (Lambda-coalescent measure trees).
Probability Theory and Related Fields 145(1-2), 2009. Free preprint is available here.
• Jean-François Le Gall, Grégory Miermont: Scaling limits of random trees and planar maps. Lecture notes, Clay Mathematics Proceedings.
Available here
• David Aldous: The Continuum Random Tree I. Annals of Probability 19(1), 1991
• David Aldous: The Continuum Random Tree II: An Overview. Stochastic Analysis, 1991
• David Aldous: The Continuum Random Tree III. Annals of Probability 21(1), 1993
• Thomas Duquesne, François Le Gall: Random trees, Lévy processes and spatial branching processes. Astérisque 281, 2002

Homepage of Wolfgang Löhr
Last updated: 2014/07/10