Scaling limits and local weak limits of random structures

该方案具有随机结构的尺度极限和局部弱极限。尺度极限描述了随机结构序列的渐近全局几何形状。这个领域在最近的文献中受到了很多关注，特别是由于Le Gall和Miermont在布朗平面地图上的开创性工作。2012年，他获得了欧洲数学学会（European Mathematical Society）的奖项。尽管缩放限制描述了全局属性，但它们不包含局部属性的信息，例如随机图中随机选择的顶点的极限度分布。随机根结构的这种渐近局部性质用局部弱极限，特别是benjamin - schramm极限来描述。这两个领域都在概率论和组合学之间架起了一座有趣的桥梁。这一领域以前的大部分工作都是处理有序结构和标记图。除了对无序树的一些研究结果外，对随机无标记结构（即被认为是对称的结构）的了解相对较少。本项目的主要重点是建立更复杂的随机无标记图模型的局部弱极限和缩放极限。首先，我们考虑亚临界图类的随机图，这在最近的文献中得到了一些关注。在这里，根据图是标记的、未标记的和有根的，还是未标记的和无根的来区分三种不同的模型。我们之前已经建立了标记情况下和未标记根图的极限。一个重要的挑战是获得无根顶点的未标记图的极限，因为这类对象的自同构具有更复杂的结构。我们的方法使用了由Bodirsky等人开发的称为循环指向的组合技术。我们在之前的工作中使用了这种方法，证实了Aldous关于随机无标记无根树的缩放极限的猜想，并在此设置中应用它，我们的目标是获得随机无标记图的缩放极限和benjami - schramm极限。其次，我们考虑随机无标记的k维树，这是推广树的图论概念的图。从组合的角度来看，这些对象很有趣，因为它们的枚举有很长的历史；从算法的角度来看，它们很有趣，因为图上的许多np困难问题在限制在k维树时都有多项式算法。我们的目标是获得无根或根在(k+1)-团的随机无标记k维树的标度极限和局部弱极限。我们的方法基于Gainer-Dewar和Gessel（2014）的枚举结果，以及申请人（2015）开发的关于随机富集树的方法。

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.