Scaling limits and local weak limits of random structures

• Applicant: Dr. Benedikt Stufler
• Subject Area: Mathematics
• Term: from 2016 to 2017
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 315422461

The proposal features scaling limits and local weak limits of random structures.Scaling limits describe the asymptotic global geometric shape of a sequence of random structures. This field has received much attention in recent literature, particularly due to the pioneering work by Le Gall and Miermont on the Brownian Planar Map. This was acknowledged by awarding a prize of the European Mathematical Society to Miermont in 2012.Although scaling limits describe global properties, they do not contain information on local properties, such as the limiting degree distribution of a randomly chosen vertex in a random graph. Such asymptotic local properties of random rooted structures are described by local weak limits, in particular by Benjamini-Schramm limits. Both fields build an interesting bridge between probability theory and combinatorics.Most previous work in this area treats ordered structures and labelled graphs. Except for some results on unordered trees, relatively little is known about random unlabelled structures, i.e. structures considered up to symmetry. The main focus of the present project is to establish local weak limits and scaling limits of more complex models of random unlabelled graphs. First, we consider random graphs from subcritical graph classes, which received some attention in recent literature. Here one distinguishes between three different models depending on whether the graphs are labelled, unlabelled and rooted, or unlabelled and unrooted. We have previously established limits in the labelled case and for unlabelled rooted graphs. A significant challenge is to obtain limits for unlabelled graphs without root vertices, as the automorphisms of such objects have a more complicated structure. Our method uses a combinatorial technique called cycle pointing, which was developed by Bodirsky et al. We used this approach in previous work that confirms a conjecture by Aldous regarding the scaling limit of random unlabelled unrooted trees, and applying it in this setting we aim to obtain scaling limits and Benjamini-Schramm limits of random unlabelled graphs.Second, we consider random unlabelled k-dimensional trees, which are graphs that generalize the graph theoretic concept of trees. These objects are interesting from a combinatorial point of view, as their enumeration has a long history, and they are interesting from an algorithmic point of view, as many NP-hard problems on graphs have polynomial algorithms when restricted to k-dimensional trees. We aim to obtain scaling limits and local weak limits of random unlabelled k-dimensional trees that either have no root or are rooted at a (k+1)-clique. Our approach is based on enumerational results by Gainer-Dewar and Gessel (2014), and methods developed by the applicant (2015) regarding random enriched trees.

• DFG Programme: Research Fellowships
• International Connection: France
• Host: Professor Dr. Grégory Miermont