Overlap properties of geometric expanders
Overlap properties of geometric expanders
复制标题
几何扩展器的重叠特性
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
J. Pach
中科院分区：
文献类型：
--
作者：
J. Fox;M. Gromov;V. Lafforgue;A. Naor;J. Pach
摘要有限的重叠数（d+1） - 均匀的超图H是最大的常数c（h）（h）（0，1），因此，无论我们如何将h的顶点映射到ℝD中，都有一个涵盖的点至少是由其超中心图像引起的简单的C（h）分数，这是通过寻找图形扩展概念的较高维度简单复合物的类似物。大型（D+1） - 具有随机方法和显式构造的有界程度的均匀的超图，我们通过构造（D+1）均匀的超图的无限族，以其重叠数量为从下方界定正常数C = C（D），我们还表明，对于每个D不对称地等于具有N顶点的完整（D+1） - 均匀的超图，作为N→，我们为任何H建立了以下几何分区，s和任何ɛ> 0，存在k = k（ɛ，h，s），可满足任何k k的条件。描述大多数s的复杂性，每个有限集p⫅ℝd都有一个分区p = p1 p = p1 pk到大小的k部分，尽可能地相等，以至于除最多的H-tupers（PI1，… ，pih）具有每个PIJ中一个具有一个元素的点的H-tupers均与R相关，或者没有一个元素。
Abstract The overlap number of a finite (d + 1)-uniform hypergraph H is the largest constant c(H) ∈ (0, 1] such that no matter how we map the vertices of H into ℝd, there is a point covered by at least a c(H)-fraction of the simplices induced by the images of its hyperedges. Motivated by the search for an analogue of the notion of graph expansion for higher dimensional simplicial complexes, we address the question whether or not there exists a sequence of arbitrarily large (d + 1)-uniform hypergraphs with bounded degree for which . Using both random methods and explicit constructions, we answer this question positively by constructing infinite families of (d + 1)-uniform hypergraphs with bounded degree such that their overlap numbers are bounded from below by a positive constant c = c(d). We also show that, for every d, the best value of the constant c = c(d) that can be achieved by such a construction is asymptotically equal to the limit of the overlap numbers of the complete (d + 1)-uniform hypergraphs with n vertices, as n → ∞. For the proof of the latter statement, we establish the following geometric partitioning result of independent interest. For any h, s and any ɛ > 0, there exists K = K(ɛ, h, s) satisfying the following condition. For any k ≧ K and for any semi-algebraic relation R on h-tuples of points in a Euclidean space ℝd with description complexity at most s, every finite set P ⫅ ℝd has a partition P = P1 ∪ ⋯ ∪ Pk into k parts of sizes as equal as possible such that all but at most an ɛ-fraction of the h-tuples (Pi1, … , Pih) have the property that either all h-tuples of points with one element in each Pij are related with respect to R or none of them are.