Combinatorial structures and algorithms: Phase transition, enumeration, and sampling

Speaker: Mihyun Kang

Affiliation: Humboldt U. at Berlin, Germany

Abstract: Random discrete structure, such as random graphs, discrete random processes, random graphs with constraints, have been extensively studied during the last few decades and have become one of the central themes of contemporary mathematics and computer science. This is partly because they are useful for both designing and analyzing algorithms that answer fundamental, structural and algorithmic questions arising in discrete mathematics and computer science and provide a wide potential range of applications. Major topics include phase transition, enumeration and random sampling.

The phase transition is a phenomenon that appears in natural sciences in various contexts, which refers to a phenomenon that a small change of parameters of a system near the critical value can significantly affect its globally observed behaviour. This phenomenon can be observed in particular in statistical physics, percolation and computational problems in computer science such as MAX-CUT and SAT.

Enumeration is a basic, essential tool in the study of combinatorial structures. In order to investigate asymptotic properties of a typical combinatorial structure of interest, one computes certain quantities in question and conclude the desired property, with additional help of large deviation inequalities from the probability theory. For such computations one often uses recursive methods or singularity analysis of generating functions.

Random sampling or random generation plays an important role in combinatorics and in computer science as well as in statistical mechanics. When a speculating model of a complex system is too complicated to analyze, it is often very useful to have information on empirical properties gathered through random sampling and simulation. Beyond empiricaly study, certain random sampling algorithms, e.g. Boltzmann sampler, can be used to theoretically determine asymptotic properties.

In this talk we discuss recent results on phase transition in various random graph models, enumeration of planar structures, and random sampling algorithms.