论文标题
随机立方平面图
Random cubic planar maps
论文作者
论文摘要
我们分析了均匀的随机立方根平面图，并获得了一些感兴趣的参数的限制分布。从列举的角度来看，我们提出了一种列举几类立方平面图的统一方法，这使我们能够以更一般和透明的方式恢复已知的结果。这种方法使我们能够获得新的列举结果。 关于随机地图，我们首先获得了根部面的分布，该图的分布具有指数尾部，如其他类别的随机图。我们的主要结果是最大块$ l $的尺寸的限制地图仪分配法，其期望在带有$ n+2 $ faces的随机立方地图中渐近$ n/\ sqrt {3} $。我们证明了最大立方块的大小的结果，从$ l $中删除了所有第二级的顶点，以及最大的3个连接组件的大小，其预期值分别为$ n/2 $和$ n/4 $。为了获得这些结果，我们需要分析Banderier等人尚未处理的新型组成方案。 [随机结构算法2001]。
We analyse uniform random cubic rooted planar maps and obtain limiting distributions for several parameters of interest. From the enumerative point of view, we present a unified approach for the enumeration of several classes of cubic planar maps, which allow us to recover known results in a more general and transparent way. This approach allows us to obtain new enumerative results. Concerning random maps, we first obtain the distribution of the degree of the root face, which has an exponential tail as for other classes of random maps. Our main result is a limiting map-Airy distribution law for the size of the largest block $L$, whose expectation is asymptotically $n/\sqrt{3}$ in a random cubic map with $n+2$ faces. We prove analogous results for the size of the largest cubic block, obtained from $L$ by erasing all vertices of degree two, and for the size of the largest 3-connected component, whose expected values are respectively $n/2$ and $n/4$. To obtain these results we need to analyse a new type of composition scheme which has not been treated by Banderier et al. [Random Structures Algorithms 2001].
