***** KAIST Discete Math Semianr *****
DATE: March 20th, Thursday
TIME: 3PM-4PM
PLACE: E6-1, ROOM 1409
SPEAKER: Mihyun Kang, Humboldt-Universität zu Berlin, Germany.
TITLE: Enumeration and uniform sampling of planar structures
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. Using the decomposition tree we derive recursive counting formulas, from which we can design a uniform sampling algorithm to sample a random instance. Furthermore, we 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 traces 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. A natural question is whether the method may as well be applied to the enumeration of graphs embeddable on a 2-dimensional surface. This can be done by applying the matrix integral to combinatorially defined functions, in order to loosen the strong connection between maps and the traces.
----------------------------------------------
Informations on future talks can be found at :
http://math.kaist.ac.kr/~sangil/seminar.php
Please email to sangil at kaist.edu if you wish to receive this
announcements in the future by email.