Asymptotic properties of graphs on a surface

Since the foundation of the theory of random graphs by Erdos and Rényi five decades ago, various random graphs have been introduced and studied. One example is random graphs on a surface, in particular random planar graphs. Graphs on a 2-dimensional surface and related objects (e.g. planar graphs, triangulations) have been among the most studied objects in graph theory, enumerative combinatorics, discrete probability theory, and statistical physics. The main objectives of this project are to study the asymptotic properties and limit behaviour of random graphs on a surface (e.g. evolution, phase transition, critical behaviour, component size distribution) and to investigate enumerative and algorithmic aspects of unlabelled graphs on a surface (e.g. connectivity, symmetry, decomposition, random generation). This project aims to provide solutions to important and challenging open problems that call for further focused effort in view of recent developments in the field. The subject of the project is structured into three guiding themes, which are closely related and in which the following goals will be accomplished. I. Random graphs on a surface Component structure of random complex planar graphs Critical behaviour of random graphs on a surface Threshold for the chromatic number of random planar graphs II. Enumeration of unlabelled graphs on a surface Asymptotic number of unlabelled planar graphs Asymptotic number of unlabelled graphs on a surface with positive genus Systematic strategy for a constructive decomposition along symmetries III. Walsh-Boltzmann sampler for unlabelled graphs on a surface Walsh-Boltzmann sampler for planar case Walsh-Boltzmann sampler for arbitrary genus case Decomposition strategy incorporating symmetries and cycle-pointing In comparison with the classical Erdos-Rényi random graph, additional constraints imposed on graphs (e.g. planarity, genus, symmetry) lead to serious difficulties in the analysis and require interplay between the theory of random graphs, structural graph theory, enumerative combinatorics, analytic combinatorics, and algorithmic graph theory. To achieve the objectives of the project, it will be necessary to advance existing approaches and develop new techniques which combine probabilistic methods, graph theoretic methods, methods from analytic combinatorics (e.g. singularity analysis, saddle point method), and algorithmic methods (e.g. Boltzmann sampler).

The scientic goal of the project was to study the asymptotic properties and limit behavior of random graphs on a surface and to investigate enumerative and algorithmic aspects of unlabelled graphs on a surface. The whole project has been successfully carried out and the scientic goals of the project are achieved. The signicant achievements of the project are vefold. (1)We have successfully accomplished the scientific goals set for the project. (2)The research results obtained through the project have been published or submitted for publication in leading peer-reviewed journals or peer-reviewed conference proceedings 18 papers in total. (3)The scientific results of the project have led to one PhD thesis and one Master thesis and will form a base for one Habilitation thesis. (4)The signicant results are disseminated also in important international scientic conferences. (5)On top of these scholarly achievements, the additional gain of the project is that the project leader has strengthened the existing collaborations and have successfully expanded new collaborations with leading experts. The most signicant scientic results of the project involve (a) triangulations and cubic graphs on surfaces; (b) random graphs on surfaces; (c) genus of Erdos-Rényi random graphs; (d) cohomology groups of random simplicial complexes. Possible applications to other sciences concern the analysis of fundamental aspects of large complex networks (e.g. neurons in the brain, man-made and natural networks, ecological networks, and social networks etc.). In the past, various models of random graphs have successfully been used to study such networks.