Scaling limits and local weak limits of random structures

该方案刻画了随机结构的尺度极限和局部弱极限，尺度极限描述了随机结构序列的渐近全局几何形状。这个领域在最近的文献中受到了很大的关注，特别是由于Le Gall和Miermont在布朗平面映射上的开创性工作。2012年，欧洲数学学会授予Miermont一个奖项，承认了这一点。尽管比例限制描述了全局属性，但它们不包含关于局部属性的信息，例如随机图中随机选择的顶点的极限度分布。随机根结构的这种渐近局部性质可以用局部弱极限来描述，特别是用Benjamini-Schramm极限来描述。这两个领域在概率论和组合学之间建立了一座有趣的桥梁。这一领域的大多数以前的工作都是处理有序结构和标号图。除了关于无序树的一些结果外，关于随机无标记结构，即被认为达到对称性的结构，人们所知的相对较少。本项目的主要目的是建立更复杂的随机无标号图模型的局部弱极限和标度极限。首先，我们考虑来自次临界图类的随机图，这在最近的文献中受到了一些关注。这里根据图是有标记的、无标记的和有根的，还是无标记的和无根的，来区分三种不同的模型。我们以前已经在有标号的情况下和无标号有根图中建立了极限。一个重要的挑战是获得没有根点的无标号图的极限，因为这类对象的自同构具有更复杂的结构。我们的方法使用了一种称为循环指向的组合技术，该技术是由Bodirsky等人开发的。我们在以前的工作中使用了这种方法，证实了Aldous关于随机无标号树的尺度极限的猜想，并将其应用于此背景下，我们的目的是得到随机无标号图的标度极限和Benjamini-Schramm极限。从组合的观点来看，这些对象很有趣，因为它们的计数有很长的历史，从算法的角度来看，它们很有趣，因为当限制到k维树时，图上的许多NP-Hard问题都有多项式算法。我们的目的是得到随机无标号k维树的标度极限和局部弱极限，这些树要么没有根，要么根于(K1)团。我们的方法是基于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.