Source-linked AI summary
Overlap properties of geometric expanders
Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, Janos Pach
TL;DR
The paper addresses whether arbitrarily large bounded-degree hypergraphs can have overlap numbers bounded away from zero, a higher-dimensional analogue of graph expansion. It constructs such families using random and explicit methods and proves a geometric partition result. The best bounded-degree overlap is asymptotically the limit for complete hypergraphs.
Problem
It was open whether arbitrarily large bounded-degree (d + 1)-uniform hypergraphs could have overlap numbers bounded below by a positive constant, as a higher-dimensional analogue of graph expansion.
Source: §1 · p. 2Method
The paper uses randomized constructions, explicit constructions from building quotients, and a geometric partition theorem to establish bounded-degree overlap results.
Source: §1 · p. 3Results
For each dimension, bounded-degree families attain overlap arbitrarily close to c(d), the limiting overlap of complete (d + 1)-uniform hypergraphs.
Source: §1 · pp. 4–5Takeaways & Limitations
For sufficiently large bounded-degree hypergraphs with enough nonisolated vertices, c(d) is the largest asymptotically achievable overlap.
Source: §1 · p. 5For d ≥ 3, it remains unknown whether arbitrarily large bounded-degree complexes are highly overlapping under non-affine embeddings.
Source: §10 · p. 27
Abstract
from arXiv · showhide
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}^\infty$ of arbitrarily large $(d+1)$-uniform hypergraphs with bounded degree, for which $\inf_{n\ge 1} 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 $n\rightarrow\infty$. 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)\ge d+1$ satisfying the following condition. For any $k\ge K$, for any point $q \in \mathbb{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 \cup \ldots \cup 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$.
1. Introduction
The paper answers Gromov’s question by constructing bounded-degree hypergraph families whose overlap numbers stay positive. It also characterizes the best achievable overlap for bounded-degree families through the limiting overlap of complete hypergraphs, using a geometric partition theorem.
1. Introduction
- The introduction frames bounded-degree overlap as a higher-dimensional analogue of graph expansion and poses the existence of such families as Gromov’s question.For 2-dimensional complexes, the question asks whether sparse triangle systems retain the overlap property known for all triangles determined by points in the plane.Source: §1 · pp. 2–3
- Theorem 1.3 gives arbitrarily large 3-uniform hypergraphs of degree k with overlap at least 2/9 − ε, and 2/9 cannot be improved.For every ε > 0, the degree k depends on ε.Source: §1 · p. 3
- For every d ≥ 2, Theorem 1.4 gives arbitrarily large (d + 1)-uniform hypergraphs of degree k_d with overlap at least c_d > 0.Source: §1 · p. 3
- For odd primes p and r ≥ 3, certain Cayley-graph clique hypergraphs on PGL_r(F_{p^m}) have positive overlap for arbitrarily large m.Their generating sets have size bounded in terms of p and r.Source: §1 · p. 4
- For fixed dimension and maximum degree, sufficiently large hypergraphs have overlap at most c(d) + ε; regular constructions attain at least c(d) − ε.Together, these bounds make c(d) the largest possible overlap asymptotically for bounded-degree hypergraphs with sufficiently many nonisolated vertices.Source: §1 · p. 5
- Theorem 1.8 partitions R^d into k equal-measure parts so that all but an ε-fraction of their (d + 1)-tuples are homogeneous with respect to q.The result holds for sufficiently large k and finite Borel measures assigning zero measure to every hyperplane.Source: §1 · p. 5
2. A topological proof of the Boros-F¨uredi theorem
The proof reduces the planar overlap claim to finding a point from which no ray is exposed. A topological contradiction establishes such a point, which then lies in many triangles.
2. A topological proof of the Boros-F¨uredi theorem
- Assuming every point has an exposed ray, the proof builds a set of point-direction pairs whose fibers are nonempty proper intervals.The exposed-ray condition uses rays meeting fewer than n^2/9 segments; the construction includes directions lying between exposed rays across a region containing fewer than n/3 points.Source: §2 · pp. 6–7
- A point with no exposed ray guarantees at least n^3/27 triangles containing it, by counting edges crossed by opposite rays.Each edge counted with a point of the set spans a triangle containing the chosen point; each triangle is counted at most three times.Source: §2 · p. 6
- A fixed-point lemma forces a point-direction pair into the complementary set, contradicting the interval-fiber properties.The contradiction uses the fact that the fibers are nonempty proper closed intervals and the topology of the projections.Source: §2 · p. 7
3. Sparse constructions using the probabilistic method
The section constructs bounded-degree hypergraphs probabilistically, with separate planar and higher-dimensional arguments. Random partitions support both constructions, while the planar overlap bound is nearly optimal and the higher-dimensional bounds are not maximal.
3. Sparse constructions using the probabilistic method
- Randomized constructions give bounded-degree hypergraphs with positive overlap; the planar bound is nearly optimal, while the higher-dimensional overlap is far from maximal.The construction uses a non-uniformly random choice; uniformly random regular hypergraphs also have positive overlap with high probability when degree is sufficiently large depending on dimension.Source: §3 · p. 7
3.1. Highly overlapping triple systems—Proof of Theorem 1.3.
- For the planar construction, random equal-size partitions produce a 3-uniform hypergraph, and a concurrent-line partition argument supplies a point contained in many induced triangles.The random partitions are chosen to limit intersections between parts and control how often a subset is concentrated in parts; Ceder's lemma divides the embedded points among six angular regions.Source: §3.1 · pp. 7–9
3.2. Higher dimensions—Proof of Theorem 1.4.
- In higher dimensions, random partitions and disjoint subsets whose cross-simplices share a point yield bounded-degree hypergraphs with positive overlap.The proof extends the subsets from Pach's theorem to an equipartition and controls how parts intersect them using the partition lemma.Source: §3.2 · p. 10
4. Deterministic constructions using expander graphs
Deterministic constructions based on expander graphs provide alternative proofs of the planar and higher-dimensional overlap results, with significantly better degree bounds. The planar bound is nearly optimal, but the higher-dimensional bound is not.
4. Deterministic constructions using expander graphs
- Expander-based deterministic constructions give alternative proofs of both overlap results and significantly improve their degree bounds.The planar deterministic construction, like the earlier probabilistic one, is nearly optimal; neither approach achieves a nearly optimal bound in higher dimensions.Source: §4 · pp. 10–11
4.1. Highly overlapping triple systems—second proof of Theorem 1.3.
- In the plane, a quadrilateral-free regular graph defines triples from graph neighborhoods, and the expander mixing lemma supports the overlap argument.The construction uses a six-partition associated with three concurrent lines; quadrilateral-freeness ensures the relevant neighborhood triples are not duplicated across vertices.Source: §4.1 · pp. 11–12
4.2. Higher dimensions—second proof of Theorem 1.4.
- In higher dimensions, simplices are built from non-returning walks of length d in an expander graph, yielding a common point for many simplices.The construction uses disjoint subsets whose cross-simplices have a common point, and expander spectral bounds complete the deterministic proof.Source: §4.2 · pp. 12–13
5. Finite quotients of buildings
The section constructs finite quotients of buildings whose face hypergraphs have overlap bounded below. It obtains such families from suitable lattices and applies the result to Ramanujan complexes.
5. Finite quotients of buildings
- The proof of the overlap bound uses a proportion estimate for faces containing selected vertices of each type.Proposition 5.1 supplies this estimate, and Corollary 5.3 applies it to the subsets obtained from a geometric overlap theorem.Source: §5 · pp. 15–16
- For Ramanujan complexes, improving the estimate in (10) still leaves exponent −1 in (11).The preceding bound uses a single-root strongly orthogonal system; even optimal bounds do not improve that exponent for (−1, 0, ..., 0, 1).Source: §5 · pp. 14, 16
- For sufficiently large q, the face hypergraph XI has overlap bounded below by a positive constant depending only on |I|.Applying this to finite-index subgroups produces highly overlapping families; when I = Z/rZ, the hyperedges are images of building chambers.Source: §5 · pp. 16–17
- A cocompact lattice and a sequence of finite-index subgroups with growing index can be chosen to satisfy condition (C).The construction first chooses an arithmetic subgroup, then passes to finite-index subgroups to ensure the condition.Source: §5 · p. 17
- Theorem 1.5 follows by applying Corollary 5.3 to Ramanujan complexes, while ensuring their lattices preserve type and satisfy condition (C).The section cites constructions in and alternatively.Source: §5 · p. 17
6. A Szemer´edi-type theorem for infinite hypergraphs
The section proves an equal-measure partition theorem for infinite hypergraphs with a non-atomic measure. Its key hypothesis is that the hypergraph is structured, meaning large subsets can be found that are homogeneous.
6. A Szemer´edi-type theorem for infinite hypergraphs
- For each k above K(h, c, ε), a (c, µ)-structured h-uniform hypergraph admits an equal-measure partition with at most an ε-fraction of h-tuples nonhomogeneous.The measure µ is non-atomic.Source: §6 · p. 18
- The proof first finds an equal-measure h-partition retaining density, then repeatedly raises density on subsets until it finds a superregular tuple.The density-improvement step is iterated only finitely many times before a superregular tuple is obtained.Source: §6 · pp. 18–20
- A dense h-uniform hypergraph contains a (γ, δ)-superregular h-tuple whose product measure is at least αµ(V)^h.This holds when d(G) ≥ 8δ, with α depending on γ, δ, and h.Source: §6 · p. 20
- A (c, µ)-structured hypergraph has a collection of at most L homogeneous h-tuples covering at least 1 − ε edge density.The bound L depends on h, c, and ε.Source: §6 · p. 20
7. A partition result—Proof of Theorem 1.8
For d = 2, the proof partitions the plane around q into equal-measure cones, yielding mostly homogeneous triples. The general argument builds homogeneous subsets using hyperplanes through q and applies the infinite-hypergraph partition theorem.
7. A partition result—Proof of Theorem 1.8
- In the plane, an equal-measure partition into k parts has at most an ε-fraction of nonhomogeneous triples when k is sufficiently large.The proof uses radial cones around q and bounds the number of triples whose cones intersect reflections of one another.Source: §7 · p. 22
- A point belongs to a simplex exactly when every nonempty proper vertex subset can be separated from its complement by a hyperplane through that point.Radon’s theorem supplies the converse direction of the criterion.Source: §7 · p. 22
- The ham sandwich lemma provides a hyperplane through q bisecting each of d−1 measurable sets, supporting the iterative subset construction.The resulting homogeneous sets make the hypergraph of tuples whose simplices contain q structured, so Theorem 6.1 yields Theorem 1.8.Source: §7 · pp. 22–23
- For any d, measurable sets admit subsets retaining at least a cd-fraction of each measure that are homogeneous with respect to q.The proof takes cd = 2^(2−2^(d+1)).Source: §7 · pp. 22–23
8. Optimal sparse constructions in space—Proof of Theorem 1.7
The proof constructs regular hypergraphs whose edges are uniformly distributed across large disjoint vertex sets. Combining this property with an equipartition around a common point gives overlap at least c(d) − ε.
8. Optimal sparse constructions in space—Proof of Theorem 1.7
- A sufficiently large regularity r ensures that edges are uniformly distributed across every collection of disjoint vertex subsets of size at least n/k.Such r-regular hypergraphs exist with probability tending to 1 as n grows.Source: §8 · p. 24
- An equipartition can make all but an ε/8-fraction of part-tuples homogeneous with respect to q.The proof also bounds the fraction of point-tuples whose vertices fail to occupy distinct parts.Source: §8 · p. 24
- At least a c(d) − ε fraction of hyperedges induce simplices containing q, so c(H) ≥ c(d) − ε.The proof transfers the point-overlap guarantee through homogeneous parts of an equipartition.Source: §8 · p. 24
9. Sparse hypergraphs with nearly maximal overlap number
The section proves that sufficiently large bounded-degree hypergraphs can be bijected to any point set whose simplices have overlap at most c, keeping the mapped hyperedges’ overlap at most c + ε. A uniformly random bijection has the desired property with high probability.
9. Sparse hypergraphs with nearly maximal overlap number
- For the stated size bound, every qualifying point set admits a bijection from H whose mapped hyperedges have overlap at most c + ε.The point set must have no point contained in more than a fraction c of its simplices; H must have maximum degree ∆ and no isolated vertices.Source: §9 · p. 24
- A uniformly random bijection has the desired property with high probability, and the proof says it holds almost surely.The proof controls at most nd^2 representative regions and applies a union bound over the associated hypergraphs.Source: §9 · pp. 25–27
- Azuma’s inequality bounds the martingale increments by ∆(2k + 1) when vertices are exposed one at a time.The martingale counts hyperedges mapped to hyperedges; its increments are controlled by the maximum degree of H.Source: §9 · pp. 25–26
10. Concluding remarks
The concluding remarks contrast affine overlap with results and open questions for more general embeddings. They also point to a separate question about overlap in sparse triangle systems.
10. Concluding remarks
- Gromov’s construction extends the planar result to sufficiently regular Jordan arcs, but for d ≥ 3 bounded-degree highly overlapping complexes under non-affine embeddings remain unknown.The stated mapping conditions include continuity, nowhere-dense edge images, and face restrictions that are at most r-to-1; the resulting bounds depend on r.Source: §10 · p. 27
- When the graph has girth greater than 2d, the constructed complexes admit a retraction that makes the generalized-simplex overlap conclusion fail.The retraction is continuous and piecewise affine onto the 1-skeleton, illustrating that affine overlap does not automatically extend to continuous, piecewise affine arcs.Source: §10 · p. 27
- For sparse systems of triangles, the cited general lower bound is roughly t^3/n^6, which the authors say is probably weak for most parameter values.The related question asks for the largest guaranteed overlap among systems of at least t triangles induced by n planar points.Source: §10 · p. 27