## Combinatorial structures and algorithms: Phase transition, enumeration, and 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. | |