Monday, May 10, 2010
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
room MA 041
Lecture - 14:15
In this talk we present recent results on the number of labelled planar graphs and corresponding enumeration methods. We also discuss the power and limitations of each method. In addition we discuss typical properties of planar graphs.
Gimenez and Noy recently settled the long-standing open problem of determining the asymptotic number of labelled planar graphs with $n$ vertices and $M$ edges, using the singularity analysis of generating functions. The number of edges considered in the work of Gimenez and Noy is restricted to be of the form $an$ for $1 < a <3$. In this range of $M$, a random planar graph $P(n,M)$ contains a large component of size $n-O(1)$, all planar graphs of finite size appear as its subgraphs. Thus, it corresponds to late stages of the evolution of the Erdos-Renyi random graph $G(n,M)$. Kang and Luczak studied the number of planar graphs and its typical properties in a more interesting range, when $M\le n$, combining counting arguments with analytic and probabilistic techniques. Apart from these methods, the matrix integral method from theoretical physics was successfully applied to planar graphs. Kang and Loebl showed that the enumeration of graphs embeddable on a surface can be formulated as the Gaussian matrix integral of an ice-type partition function, where the number of planar graphs appears as a leading term.
Colloquium - 16:00
The normal Euler class for a simplicial surface in four-space can be defined by analogy with the geometric description of this class for a smooth surface. We present a combinatorial formula for the normal Euler class in terms of the self-linking numbers of spherical polygons and inflection faces of polyhedra, related to a construction of Gromov, Lawson, and Thurston. The talk will feature computer graphics illustrations.