Monday, June 23, 2008
Freie Universität Berlin
Institut für Informatik
Takustr. 9,
room 005
Lecture - 14:15
Abstract:
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
Abstract: