Séminaire du 1er octobre 2007,
10h30: Enumeration and uniform sampling of planar structures . Mihyun Kang, Humboldt-Universität zu Berlin, Institut für Informatik.
Planar structures, particularly planar graphs, have attracted much attention during the last few
years, from the viewpoints of enumeration, sampling and typical properties. In order to determine
the number of graphs of interest, typically graphs are decomposed according to connectivity. Thanks to the decomposition tree, we can either derive recursive counting formulas, from which we can design a uniform sampling algorithm to generate a random instance or interpret the decomposition in terms of equations of generating functions, from which we can estimate the asymptotic numbers using singularity analysis. On the other hand, the
matrix integral method, a technique of theoretical physics, employs the powers of Hermitian matrices to express the number of embedded graphs on a 2-dimensional surface and planar maps in particular.
This leads to the map enumeration results analogous to those obtained by combinatorial methods. In this talk I will discuss recent results on enumeration and uniform sampling of planar structures as well as their typical properties.
Virginie Collette
Last modified: Mon May 23 18:32:54 CEST 2005