On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
复制标题
关于随机无环有向图中最大强独立顶点数
DOI：
10.1137/0605049
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
P. Erdös
中科院分区：
文献类型：
--
作者：
A. Barak;P. Erdös
设$\mathcal{A}_n $表示从顶点集$\{ 1,2, \cdots ,n\} $的随机图中得到的随机无环有向图，使得每条边都以规定的概率p出现，并且所有边都从高索引点向低索引点有向。如果子集中任何一对顶点之间没有有向路径，则将$\mathcal{A}_n $中的顶点子集定义为强独立的。我们证明了序列$\mathcal{J}(\mathcal{A}_n )$, $\mathcal{A}_n $的最大强独立顶点子集中的顶点数满足于趋向于1的概率，\[ \frac{\mathcal{J} (\mathcal{A}_n )}{\sqrt{\log n}} \to \frac{\sqrt{2 }}{\sqrt{\log 1/q}}\quad {\text{as}}\,n \to \infty , \]其中$q=1-p$。
Let $\mathcal{A}_n $ denote a random acyclic directed graph which is obtained from a random graph with vertex set $\{ 1,2, \cdots ,n\} $, such that each edge is present with a prescribed probability p and all the edges are directed from higher to lower indexed vertices. Define a subset of vertices in $\mathcal{A}_n $ to be strongly independent if there is no directed path between any pair of vertices in the subset. We show that the sequence $\mathcal{J}(\mathcal{A}_n )$, the number of vertices in the largest strongly independent vertex subset of $\mathcal{A}_n $ satisfies with probability tending to 1, \[ \frac{\mathcal{J} (\mathcal{A}_n )}{\sqrt{\log n}} \to \frac{\sqrt{2 }}{\sqrt{\log 1/q}}\quad {\text{as}}\,n \to \infty , \] where $q=1-p$.