2010/05/09 by Jacob Fox, Mikhail Gromov, Fox, Jacob +9 · 2 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Point processes and geometric inequalities #Topological and Geometric Data Analysis #cs.CG #math.CO
paper · pdf · doi:10.48550/arxiv.1005.1392
arxiv created 2010/05/09 · openalex publication_date 2010/05/09 · arxiv updated 2010/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The \em overlap number of a finite (d+1)-uniform hypergraph H is defined as the largest constant c(H)∈ (0,1] such that no matter how we map the vertices of H into \Rd, there is a point covered by at least a c(H)-fraction of the simplices induced by the images of its hyperedges. In~\citeGro2, motivated by the search for an analogue of the notion of graph expansion for higher dimensional simplicial complexes, it was asked whether or not there exists a sequence \Hn\n=1^∞ of arbitrarily large (d+1)-uniform hypergraphs with bounded degree, for which infn≥ 1 c(Hn)>0. 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 d and any ε>0, there exists K=K(ε,d)≥ d+1 satisfying the following condition. For any k≥ K, for any point q ∈ ℝd and for any finite Borel measure μ on ℝd with respect to which every hyperplane has measure 0, there is a partition ℝd=A1 ∪ … ∪ Ak into k measurable parts of equal measure such that all but at most an ε-fraction of the (d+1)-tuples Ai1,…,A_id+1 have the property that either all simplices with one vertex in each Aij contain q or none of these simplices contain q.