Fakultät für Mathematik, Campus Essen
Lecture with Block Seminar (2+2 SWS), Summer 2014
Time and Room: Thursday, 10:00h - 11:45h in WSC-S-U-3.03
Content of the Lecture:
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).
- Discrete random trees
- Uniform ordered/unordered labelled/unlabelled trees
- Galton-Watson trees
- Search trees
- Continuum random trees
- Trees under excursions
- The Brownian continuum random tree (CRT)
- Convergence of trees
- Gromov-Hausdorff convergence
- Gromov-weak convergence
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.
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:
The course will be taught in English, unless all participants prefer German.
- Analysis I-III
- Probability Theory I+II
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.
- 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.
- 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