论文标题
随机二维立方体复合物的拓扑
Topology of random 2-dimensional cubical complexes
论文作者
论文摘要
我们研究了随机二维立方体复合物的自然模型，该模型是N维立方体的子复合物，并且每个可能的正方形$ 2 $ -face都独立包含在概率上。我们的主要结果是在同源性消失为$ n \ to \ infty $的同源性消失方面表现出尖锐的阈值P = 1/2。这是Burtin和Erdős-Spencer定理的二维类似物，该定理表征了随机立方图的连通性阈值。我们的主要结果也可以看作是用于随机二维简单络合物的线性 - 壳定理的立方体。但是，模型表现出极大的行为。我们表明，如果$ p> 1- \ sqrt {1/2} \大约0.2929 $，则具有很高的概率，基本组是一个免费组，每个最大$ 1 $维度的面孔都有一个发电机。作为推论，即使在强烈的“打击时间”意义上，同源性消失和简单的连通性也具有相同的阈值。这与简单的情况形成鲜明对比的是，阈值相距遥远。证明取决于迭代循环的迭代算法 - 我们表明，算法迅速而大大简化了基本组，仅在几个步骤后融合。
We study a natural model of random 2-dimensional cubical complex which is a subcomplex of an n-dimensional cube, and where every possible square $2$-face is included independently with probability p. Our main result is to exhibit a sharp threshold p=1/2 for homology vanishing as $n \to \infty$. This is a 2-dimensional analogue of the Burtin and Erdős-Spencer theorems characterizing the connectivity threshold for random cubical graphs. Our main result can also be seen as a cubical counterpart to the Linial--Meshulam theorem for random 2-dimensional simplicial complexes. However, the models exhibit strikingly different behaviors. We show that if $p > 1 - \sqrt{1/2} \approx 0.2929$, then with high probability the fundamental group is a free group with one generator for every maximal $1$-dimensional face. As a corollary, homology vanishing and simple connectivity have the same threshold, even in the strong "hitting time" sense. This is in contrast with the simplicial case, where the thresholds are far apart. The proof depends on an iterative algorithm for contracting cycles -- we show that with high probability the algorithm rapidly and dramatically simplifies the fundamental group, converging after only a few steps.
