Combinatorial Structures and Algorithms: Phase Transition, Enumeration and Sampling
Final Report Abstract
As a Heisenberg Fellow I conducted the research project "Combinatorial Structures and Algorithms: Phase Transition, Enumeration, and Sampling". Through the Heisenberg-Programme I could focus on research without teaching duties and visit experts in my research field to work together. As a consequence I have strengthened the exiting collaboration or initiated new collaborations and have achieved the objectives of the project, e.g. the study of the phase transition in random graph processes and random planar graphs, the enumeration of planar graphs, the development of efficient sampling algorithms for unlabelled combinatorial structures. During the last few decades, random combinatorial structures have been extensively studied by many scientists and have become one of the central themes of contemporary mathematics. This is partly because they are useful for modelling, analysing and solving structural and algorithmic problems arising from mathematics, theoretical computer science and natural sciences, and they provide a wide potential range of applications. A fascinating phenomenon observed in mathematics and natural sciences in various contexts is the phase transition and critical behaviour. The phase transition deals with an abrupt change in the properties of an asymptotically large structure by altering critical parameters. The phase transition in random combinatorial structure has captured the attention of many scientists, and the intense study has brought together different fields such as discrete mathematics, probability theory and theoretical computer science as well as statistical physics. Among the main mathematical results achieved through my Heisenberg Fellowship is the strengthening of qualitative similarities of the phase transition in the Bohman-Frieze processes to that in the standard random graph. The more important aspect of this work is that while solving problems I have developed a new method of investigating the phase transition of random graph processes through the singularity analysis of a quasi linear partial differential equation (PDE), which is satisfied by the moment generating function for the fraction of vertices in small components. I expect that this new method can also be applied to analysis of various random graph processes and randomised algorithms which make a sequence of random choices. The second important mathematical achievement is that I have found that there are two critical periods in the evolution of a random planar graph. The first one takes place when the giant component is formed, and it is consistent with the universal behaviour of the phase transition in the standard random graph. The second critical period takes place, when the giant component covers nearly all vertices. The second type of critical behaviour has not been observed in any other random graph model that I know of. I expect that a random graph on a surface with positive genus may also exhibit two critical periods, the first one consistent with the universal one, and the second one with critical exponent related to genus.
Publications
- The Bohman-Frieze process near criticality Random Structures and Algorithms
M. Kang, W . Perkins and J. Spencer
(See online at https://doi.org/10.1002/rsa.20437) - The enumeration of planar graphs via Wick's theorem. Advances in Mathematics 221 (2009), 1703-1724
M. Kang and M. Loebl
- Asymptotic study of subcritical graph classes, SIAM Journal on Discrete Mathematics 25 (2011), 1615-1651
M. Drmota, É. Fusy, M. Kang, V. Kraus and J. Rué
- Boltzmann samplers, Pólya theory and cycle pointing, SIAM Journal on Computing 40 (2011), 721-769
M. Bodirsky, É. Fusy, M. Kang and S. Vigerske
- Random unlabelled graphs containing few disjoint cycles, Random Structures and Algorithms 38 (2011), 174-204
M. Kang and C. McDiarmid
- The two critical phase of a random planar graph, Transactions of the American Mathematical Society 364 (2012), 4239-4265
M. Kang and T. Luczak
