论文标题
随机统一和纯随机简单复合物
Random Uniform and Pure Random Simplicial Complexes
论文作者
论文摘要
在本文中，我们介绍了一种方法，该方法使我们能够研究随机均匀的简单复合物的特性。也就是说，我们将同等概率分配给具有给定数量的顶点的所有简单络合物，然后在此度量下考虑复合物的特性。我们能够确定或呈现许多拓扑和组合特性的边界。我们还研究了尺寸$ d $的随机纯简单络合物，该复合物是通过让任何尺寸$ d+1 $ $ d+1 $的$ n $顶点的子集生成的，这是一个带有概率$ p $的面，并且考虑了这些方面产生的简单复合物。我们将这些模型的行为比较了$ d $和$ p $的合适值。 最后，我们使用简单复合物和单调布尔函数之间的等效性来研究典型的此类功能的行为。具体而言，我们证明大多数单调布尔函数都是逃避的，因此证明众所周知的逃避猜想对于没有对称假设的单调布尔函数通常是正确的。
In this paper we introduce a method which allows us to study properties of the random uniform simplicial complex. That is, we assign equal probability to all simplicial complexes with a given number of vertices and then consider properties of a complex under this measure. We are able to determine or present bounds for a number of topological and combinatorial properties. We also study the random pure simplicial complex of dimension $d$, generated by letting any subset of size $d+1$ of a set of $n$ vertices be a facet with probability $p$ and considering the simplicial complex generated by these facets. We compare the behaviour of these models for suitable values of $d$ and $p$. Finally we use the equivalence between simplicial complexes and monotone boolean functions to study the behaviour of typical such functions. Specifically we prove that most monotone boolean functions are evasive, hence proving that the well known Evasiveness conjecture is generically true for monotone boolean functions without symmetry assumptions.
