Scaling limits and local weak limits of random structures

随机结构的尺度极限和局部弱极限

• 批准号: 315422461
• 负责人: Dr. Benedikt Stufler
• 金额: --
• 依托单位: Institut für Mathematik
• 依托单位国家: 德国
• 项目类别: Research Fellowships
• 财政年份: 2016
• 资助国家: 德国
• 起止时间: 2015-12-31 至 2016-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/315422461?language=en
• 关键词: Scaling; limits; local; weak; random

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.

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