Minors in random and expanding hypergraphs
Minors in random and expanding hypergraphs
复制标题
随机和扩展超图中的未成年人
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Uli Wagner
中科院分区：
文献类型：
--
作者：
Uli Wagner
我们引入了一个新的概念，未成年人单纯复形（超图），所谓的同调未成年人。我们的动机是提出一个通用的方法来攻击某些极值问题的稀疏单纯复形和相应的阈值问题的随机复形。在本文中，我们专注于阈值问题。随机复合物的基本模型是Linial-Meshulam模型Xk（n，p）。根据定义，这样的复形有n个顶点，一个完整的（k-1）维骨架，并且每个可能的k维单形都是以概率p独立选择的。我们证明了对每个k，t ≥ 1，存在一个常数C=C（k，t），使得对p ≥ C/n，随机复形Xk（n，p）渐近几乎必然包含Kkt（t个顶点上的完整k维复形）作为同调子式。作为推论，Xk（n，p）到R2 k中的（拓扑）可嵌入性的阈值为p=Θ（1/n）。
该方法可以扩展到其他模型的随机复合体（其中较低的ESTA不一定是完整的），也更一般的Tverberg型问题，而不是连续的地图没有双重覆盖的图像点（嵌入），我们认为没有q倍覆盖的图像点的地图。
We introduce a new notion of minors for simplicial complexes (hypergraphs), so-called homological minors. Our motivation is to propose a general approach to attack certain extremal problems for sparse simplicial complexes and the corresponding threshold problems for random complexes. In this paper, we focus on threshold problems. The basic model for random complexes is the Linial-Meshulam model Xk(n,p). By definition, such a complex has n vertices, a complete (k-1)-dimensional skeleton, and every possible k-dimensional simplex is chosen independently with probability p. We show that for every k,t ≥ 1, there is a constant C=C(k,t) such that for p ≥ C/n, the random complex Xk(n,p) asymptotically almost surely contains Kkt (the complete k-dimensional complex on t vertices) as a homological minor. As corollary, the threshold for (topological) embeddability of Xk(n,p) into R2k is at p=Θ(1/n).
The method can be extended to other models of random complexes (for which the lower skeleta are not necessarily complete) and also to more general Tverberg-type problems, where instead of continuous maps without doubly covered image points (embeddings), we consider maps without q-fold covered image points.
随机 2-复合体的拓扑
影响因子：
0.8
作者：
Cohen D
通讯作者：
Cohen D