Overlap properties of geometric expanders

DOI10.1515/CRELLE.2011.157zbMATH Open1306.05171arXiv1005.1392OpenAlexW1664849218WikidataQ101499152 ScholiaQ101499152MaRDI QIDQ3168403FDOQ3168403

Authors: Jacob Fox, Vincent Lafforgue, Assaf Naor, János Pach, Misha Gromov 

Publication date: 31 October 2012

Published in: Journal für die reine und angewandte Mathematik (Crelles Journal) (Search for Journal in Brave)

Abstract: The {em overlap number} of a finite $(d+1)$-uniform hypergraph $H$ is defined as the largest constant $c(H)in(0,1]$ such that no matter how we map the vertices of $H$ into $R^d$, there is a point covered by at least a $c(H)$-fraction of the simplices induced by the images of its hyperedges. In~cite{Gro2}, 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 ${H_n}_{n=1}^{i}nfty$ of arbitrarily large $(d+1)$-uniform hypergraphs with bounded degree, for which $in{f}_{nge1}c(H_n)>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 $nightarrowinfty$. For the proof of the latter statement, we establish the following geometric partitioning result of independent interest. For any $d$ and any $epsilon>0$, there exists $K=K(epsilon,d)ged+1$ satisfying the following condition. For any $kgeK$, for any point $qinmathbb{R}^d$ and for any finite Borel measure $mu$ on $mathbb{R}^d$ with respect to which every hyperplane has measure $0$, there is a partition $mathbb{R}^d=A_{1}cupldotscup{A}_k$ into $k$ measurable parts of equal measure such that all but at most an $epsilon$-fraction of the $(d+1)$-tuples $A_{i_1},ldots,A_{i_{d+1}}$ have the property that either all simplices with one vertex in each $A_{i_j}$ contain $q$ or none of these simplices contain $q$.

Full work available at URL: https://arxiv.org/abs/1005.1392

Recommendations

• Overlap properties of geometric expanders (extended abstract)
• On expansion and topological overlap
• On expansion and topological overlap

Mathematics Subject Classification ID

Hypergraphs (05C65)

Cites Work

• The number of triangles covering the center of an \(n\)-set
• A generalization of Caratheodory's theorem
• Crossing patterns of semi-algebraic sets
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• Ramanujan graphs
• Uniform pointwise bounds for matrix coefficients of unitary representations and applications to Kazhdan constants
• Balls and bins: A study in negative dependence
• A family of \(\widetilde A_n\)-groups
• Explicit constructions of Ramanujan complexes of type \(\widetilde A_d\).
• Ramanujan complexes of type \(\widetilde A_d\)
• A Tverberg-type result on multicolored simplices
• Points and triangles in the plane and halving planes in space
• Ramanujan geometries of type \(\tilde A_{n}\)
• Ramanujan hypergraphs
• Explicit construction of a Ramanujan \((n_1,n_2,\dots,n_{d-1})\)-regular hypergraph
• Ramanujan Type Buildings
• Eppstein's bound on intersecting triangles revisited

Cited In (46)

• Regular partitions of gentle graphs
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• Random Steiner systems and bounded degree coboundary expanders of every dimension
• Ramanujan complexes and high dimensional expanders
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Random Latin squares and 2-dimensional expanders
• Strong Erdős-Hajnal properties in chordal graphs
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• Independent sets in algebraic hypergraphs
• Structure and regularity for subsets of groups with finite VC-dimension
• A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
• Inverse expander mixing for hypergraphs
• Boolean functions: influence, threshold and noise
• Ramsey-type results for semi-algebraic relations
• A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem
• Bounded degree cosystolic expanders of every dimension
• Generalizations of the Kolmogorov-Barzdin embedding estimates
• Infinite series of quaternionic \(1\)-vertex cube complexes, the doubling construction, and explicit cubical Ramanujan complexes
• Local and global expansion in random geometric graphs
• On Grids in Point-Line Arrangements in the Plane
• DOMINATION AND REGULARITY
• Bounds for Pach's selection theorem and for the minimum solid angle in a simplex
• Helly-type problems
• Mixing in high-dimensional expanders
• Erdős-Szekeres theorem for lines
• Title not available (Why is that?)
• Isoperimetric inequalities in simplicial complexes
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1
• Simplicial branching random walks
• Expander graphs in pure and applied mathematics
• The Schur-Erdős problem for semi-algebraic colorings
• A Borsuk-Ulam lower bound for sign-rank and its applications
• Hypergraph expanders from Cayley graphs
• One-sided epsilon-approximants
• Overlap properties of geometric expanders (extended abstract)
• An elementary exposition of topological overlap in the plane
• Finite quotients of Bruhat-Tits buildings as geometric expanders
• On grids in point-line arrangements in the plane
• Homogeneous selections from hyperplanes
• Boolean function analysis on high-dimensional expanders
• Local spectral expansion approach to high dimensional expanders. II: Mixing and geometrical overlapping
• Bounded \(VC\)-dimension implies the Schur-Erdős conjecture
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• Positive-fraction intersection results and variations of weak epsilon-nets
• Spectrum and combinatorics of two-dimensional Ramanujan complexes
• Random walks on Ramanujan complexes and digraphs

This page was built for publication: Overlap properties of geometric expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3168403)