Creation and Growth of Components in a Random Hypergraph Process
Creation and Growth of Components in a Random Hypergraph Process
复制标题
随机超图过程中组件的创建和增长
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Alphonse Laza Rijamamy
中科院分区：
文献类型：
--
作者：
V. Ravelomanana;Alphonse Laza Rijamamy
用l分量表示具有k条边和k(b-1) - l个顶点的连通b-均匀超图。我们证明了随机超图过程中l分量的期望创建次数趋于1，当l和b的顶点总数n趋于∞时，使得$ell = olleft (sqrt[3]{frac{n}{b}} ight)$。在相同的条件下，我们还证明了l分量的期望顶点数约为121/3 (b-1)1/3 11 /3n2/3。直接的结果是，过程中最大的l分量很可能为0 （(b-1)1/3 11 /3n2/3）。我们的研究结果揭示了随机超图相变中巨分量的大小。
Denote by an l-component a connected b-uniform hypergraph with k edges and k(b–1) – l vertices. We prove that the expected number of creations of l-component during a random hypergraph process tends to 1 as l and b tend to ∞ with the total number of vertices n such that $ell = oleft( sqrt[3]{frac{n}{b}}
ight)$. Under the same conditions, we also show that the expected number of vertices that ever belong to an l-component is approximately 121/3 (b–1)1/3 l1/3n2/3. As an immediate consequence, it follows that with high probability the largest l-component during the process is of size O( (b–1)1/3 l1/3n2/3 ). Our results give insight about the size of giant components inside the phase transition of random hypergraphs.