Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, June 23, 2008

Freie Universität Berlin
Institut für Informatik
Takustr. 9,
room 005

Lecture - 14:15

Michael Drmota (TU Wien)

Generating Functions and Central Limit Theorems

Many interesting combinatorial objects can be "counted" with help of generating functions, for example, set and integer partitions, several classes of trees and also maps and planar graphs. With help of bi- resp. multivariate generating functions it is also very convenient to encode the distribution of specific parameters. The problem is then to determine the "typical behaviour" of a parameter if the size of the object of interst goes to infinity. Actually it turns out that many parameters of interest (e.g. the number of edges in planar graphs with n vertices) satisfy a central limit theroem.

During the last 10-15 year there has been much progress in systematizing probabilistic limiting results in combinatorial structures that can be studied with help of generating functions. The purpose of this talk is to present a general result in this direction, when the corresponding generating function(s) satisfy a (system of) functional equation(s).

As applications we study the number of occurances of patterns in random trees and the degree distribution in random planar graphs.

Colloquium - 16:00



Letzte Aktualisierung: 16.06.2008