论文标题
强组件的诞生
The birth of the strong components
论文作者
论文摘要
随机定向图$ d（n，p）$在点$ p = 1/n $附近进行相变，并且自Luczak和Seierstad的工作以来，过渡窗口的宽度就已经知道。他们已经确定，当$ p =（1 +μn^{ - 1/3}）/n $时，作为$ n \ to \ infty $，随机有向图的紧密连接的组件仅是周期，单个顶点从1到0降低$ - $ $从$ - \ from $ - \ from from $ - \ from from $ - \ from from-f infty $。 通过使用分析组合学中的技术，我们建立了此概率作为$μ$的函数的确切限制值，并提供了更多的围绕其过渡点和之上的随机挖掘图的结构的属性。我们获得了一个随机挖掘物是无环的限制概率，并且它具有一个牢固连接的复杂分量的概率，边缘和顶点数量之间具有给定差异（称为多余）。我们的结果可以扩展到几个复杂组件的情况下，在整个稀疏的挖掘范围内，给定的过剩。 我们的研究基于一种通用的符号方法，该方法可以处理各种可能的挖掘家庭，以及可以系统地应用于符号方法出现的复杂轮廓积分的鞍点方法的版本。虽然技术上最简单的模型是允许多个边缘的随机多行器的模型，并且根据具有固定参数$ p $的泊松分布对边缘倍数进行独立采样，我们还显示如何系统地接近简单的digraphs家族，其中包含多个边缘的多个边缘，并且在其中允许2个网络，并且允许或不允许使用。 我们的理论预测由数值模拟支持，我们为本研究中出现的通风函数积分的数值表提供了表。
Random directed graphs $D(n,p)$ undergo a phase transition around the point $p = 1/n$, and the width of the transition window has been known since the works of Luczak and Seierstad. They have established that as $n \to \infty$ when $p = (1 + μn^{-1/3})/n$, the asymptotic probability that the strongly connected components of a random directed graph are only cycles and single vertices decreases from 1 to 0 as $μ$ goes from $-\infty$ to $\infty$. By using techniques from analytic combinatorics, we establish the exact limiting value of this probability as a function of $μ$ and provide more properties of the structure of a random digraph around, below and above its transition point. We obtain the limiting probability that a random digraph is acyclic and the probability that it has one strongly connected complex component with a given difference between the number of edges and vertices (called excess). Our result can be extended to the case of several complex components with given excesses as well in the whole range of sparse digraphs. Our study is based on a general symbolic method which can deal with a great variety of possible digraph families, and a version of the saddle point method which can be systematically applied to the complex contour integrals appearing from the symbolic method. While the technically easiest model is the model of random multidigraphs, in which multiple edges are allowed, and where edge multiplicities are sampled independently according to a Poisson distribution with a fixed parameter $p$, we also show how to systematically approach the family of simple digraphs, where multiple edges are forbidden, and where 2-cycles are either allowed or not. Our theoretical predictions are supported by numerical simulations, and we provide tables of numerical values for the integrals of Airy functions that appear in this study.
