On the phase transition in random simplicial complexes
On the phase transition in random simplicial complexes
复制标题
关于随机单纯复形的相变
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Y. Peled
中科院分区：
文献类型：
--
作者：
N. Linial;Y. Peled
众所周知，随机图的 $G(n,p)$ 模型在 $p=\frac 1n$ 周围经历了巨大的变化。正是在这里，随机图几乎可以肯定不再是森林，并且在这里它首先获得一个巨大的（即阶 $\Omega(n)$）连通分量。几年前，Linial 和 Meshulam 引入了 $X_d(n,p)$ 模型，这是一个 $n$ 顶点 $d$ 维单纯复形的概率空间，其中 $X_1(n,p)$ 与 $G(n,p)$ 重合。在这个模型中，我们证明了这些图论现象的自然 $d$ 维模拟。具体来说，我们确定来自 $X_d(n,p)$ 的复合物的真实第 $d$ 个同源性不消失的确切阈值。我们还计算 $X_d(n,p)$ 对于 $p=c/n$ 的实贝蒂数。最后，我们确定巨型阴影的出现是在这个阈值。 （对于 $d=1$，巨大的阴影和巨大的组件是等效的）。与图的情况不同，对于 $d\ge 2$ 来说，巨大阴影的出现是一阶相变。
It is well-known that the $G(n,p)$ model of random graphs undergoes a dramatic change around $p=\frac 1n$. It is here that the random graph is, almost surely, no longer a forest, and here it first acquires a giant (i.e., order $\Omega(n)$) connected component. Several years ago, Linial and Meshulam have introduced the $X_d(n,p)$ model, a probability space of $n$-vertex $d$-dimensional simplicial complexes, where $X_1(n,p)$ coincides with $G(n,p)$. Within this model we prove a natural $d$-dimensional analog of these graph theoretic phenomena. Specifically, we determine the exact threshold for the nonvanishing of the real $d$-th homology of complexes from $X_d(n,p)$. We also compute the real Betti numbers of $X_d(n,p)$ for $p=c/n$. Finally, we establish the emergence of giant shadow at this threshold. (For $d=1$ a giant shadow and a giant component are equivalent). Unlike the case for graphs, for $d\ge 2$ the emergence of the giant shadow is a first order phase transition.