Overlap properties of geometric expanders

DOI10.1515/CRELLE.2011.157MaRDI QIDQ3168403zbMATH OpenOpenAlexWikidataFDO

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)

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

Mathematics Subject Classification ID

Hypergraphs (05C65)

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$.

Recommendations

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

Cites work

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

Cited in

(45)

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

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)