OVERLAP PROPERTIES OF GEOMETRIC EXPANDERS

JACOB FOX, MIKHAIL GROMOV, VINCENT LAFFORGUE, ASSAF NAOR, AND JÁNOS PACH

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. In [17], 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}^{∞} of arbitrarily large (d+1)-uniform hypergraphs with bounded degree, for which inf_{n⩾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 → ∞. 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} = A_{1} ∪ … ∪ A_{k} into k measurable parts of equal measure such that all but at most an ε-fraction of the (d+1)-tuples A_{i_{1}}, …, 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.

Contents

1. Introduction  2
2. A topological proof of the Boros-Füredi theorem  6
3. Sparse constructions using the probabilistic method  7
3.1. Highly overlapping triple systems—Proof of Theorem 1.3  7
3.2. Higher dimensions—Proof of Theorem 1.4  10
4. Deterministic constructions using expander graphs  10
4.1. Highly overlapping triple systems—second proof of Theorem 1.3  11
4.2. Higher dimensions—second proof of Theorem 1.4  12
5. Finite quotients of buildings  13
6. A Szemerédi-type theorem for infinite hypergraphs  17
7. A partition result—Proof of Theorem 1.8  22
8. Optimal sparse constructions in space—Proof of Theorem 1.7  23
9. Sparse hypergraphs with nearly maximal overlap number  24
10. Concluding remarks  27
References  28

***Dedicated to Endre Szemerédi on his 70th birthday***.

1. Introduction

Let G = (V, E) be an n-vertex graph. Think of G as a 1-dimensional simplicial complex, i.e., each edge is present in G as an actual interval. Assume that for every subset S ⊆ V of size ⌊\frac{n}{2}⌋ the number of edges joining S and V \ S is at least α|E|, for α ∈ (0, 1]. It follows that for every f : V → ℝ, if we extend f to be a linear (or even just continuous) function defined also on the edges of G, there must necessarily exist a point x ∈ ℝ such that |f^{−1}(x)| ⩾ α|E|. Indeed, x can be chosen to be a median of the set f(V) ⊆ ℝ. In other words, no matter how we draw G on the line, its edges will heavily overlap.

As illustrated by this simple example, the above expander-like condition^{1} on G implies that all of its embeddings in ℝ satisfy a geometric overlap condition. This condition naturally extends to higher-dimensional simplicial complexes, and can thus serve as a potential definition of a higher-dimensional analogue of edge expansion^{2}. Such investigations of highdimensional geometric analogues of edge expansion were initiated by Gromov in [17]. The present paper follows this approach.

In 1984, answering a question of Kárteszi, two undergraduates at Eötvös University, Boros and Füredi [8], proved the following theorem.

Theorem 1.1 ([8]). For every set P of n points in the plane, there is a point (not necessarily in P) that belongs to at least (\frac{2}{9} − o(1)) \binom{n}{3} closed triangles induced by the elements of P.

The factor \frac{2}{9} in Theorem 1.1 is asymptotically tight, as shown by Bukh, Matoušek and Nivasch in [10]. A short and elegant “book proof” of Theorem 1.1 was given by Bukh [9]. In Section 2, we present an alternative “topological” argument.

The theorem of Boros and Füredi has been generalized to higher dimensions. Bárány [4] proved that for every d ∈ ℕ there exists a constant c_{d} > 0 such that given any set P of n points in ℝ^{d}, one can always find a point in at least c_{d}n^{d} closed simplices whose vertices belong to P. In fact, the following stronger statement due to Pach [27] holds true.

Theorem 1.2. ([27]) Every set P of n points in ℝ^{d} has d+1 disjoint ⌊c′_{d}n⌋-element subsets, P_{1}, …, P_{d+1}, such that all closed simplices with one vertex from each P_{i} have a point in common. Here c′_{d} > 0 is a constant depending only on the dimension d.

Recall that a hypergraph H = (V, E) consists of a set V and a set E of non-empty subsets of V. The elements of V are called vertices and the elements of E are called hyperedges. H is d-uniform if every hyperedge e ∈ E contains exactly d vertices. The degree of a vertex v ∈ V in H is the number of hyperedges containing v. To simplify the presentation, we introduce the following terminology.

Definition 1.1. Given a (d + 1)-uniform hypergraph H = (V, E), its overlap number c(H) is the largest constant c ∈ (0, 1] such that for every embedding f : V → ℝ^{d}, there exists a point p ∈ ℝ^{d} which belongs to at least c|E| simplices whose vertex sets are hyperedges of H, i.e., there exists a set of hyperedges S ⊆ E with |S| ⩾ c|E| and p ∈ ⋂_{e∈S} conv(f(e))

1It isn’t quite edge expansion since we do not care about boundaries of small sets.

2To be precise, what we are detecting here is only that G contains a large expander, rather than being an expander itself.

(where conv(A) denotes the convex hull of A ⊆ ℝ^{d}). An infinite family ℋ of (d + 1)- uniform hypergraphs is highly overlapping if there exists an absolute constant c > 0 such that c(H) > c for every H ∈ ℋ . An infinite family of d-dimensional simplicial complexes is called highly overlapping if the family of (d+1)-uniform hypergraphs consisting of the vertex sets of their d-dimensional faces (their d-skeletons) is highly overlapping^{3}.

Using this terminology, the Boros-Füredi theorem states that the family of all finite complete 3-uniform hypergraphs (or 2-skeletons of all complete simplicial complexes) is highly overlapping. Bárány’s theorem says that the same is true for the family of complete (d + 1)- uniform hypergraphs (or d-skeletons of complete simplicial complexes). The fact that the family of all finite complete graphs (1-skeletons of complete simplicial complexes) is highly overlapping (with c = 1/2) is trivial, but its higher dimensional generalizations are much more subtle.

It was a simple but very important graph-theoretic discovery by Pinsker [29] and others that there exist arbitrarily large edge expanders of bounded degree [18]. As we have seen at the beginning of this paper, expanders with a fixed rate of expansion are necessarily highly overlapping. This fact motivated Gromov’s question [17] whether there exist infinite families of higher dimensional simplicial complexes with bounded degree that are highly overlapping. In other words, Gromov’s question [17] for 2-dimensional simplicial complexes asks whether a Boros-Füredi type theorem remains true if instead of all triangles determined by n points in the plane, we consider only “sparse” systems of triangles. In particular, do there exist arbitrarily large 3-uniform hypergraphs H, in which every vertex belongs to at most a constant number k of triples, and whose overlap numbers are bounded from below by an absolute positive constant?

In Section 3.1, we answer this question in the affirmative, by proving the following result.

Theorem 1.3. For any ε > 0, there exists a positive integer k = k(ε) satisfying the following condition. There is an infinite sequence of 3-uniform hypergraphs H_{n} with n vertices and n tending to infinity, each of degree k, such that, for any embedding of the vertex set V (H_{n}) in ℝ^{2}, there is a point belonging to at least a (\frac{2}{9} − ε)-fraction of all closed triangles induced by images of hyperedges of H_{n}. Here the constant \frac{2}{9} cannot be improved.

We also generalize Theorem 1.3 to (d + 1)-uniform hypergraphs with d ⩾ 2.

Theorem 1.4. For every integer d ⩾ 2, there exist positive constants c_{d} and k_{d} with the following property. There is an infinite sequence of (d + 1)-uniform hypergraphs H_{n} with n vertices and n tending to infinity, each of degree k_{d}, such that, for any embedding of the vertex set V (H_{n}) in ℝ^{d}, there is a point in ℝ^{d} that belongs to at least a c_{d}-fraction of all closed simplices induced by images of hyperedges of H_{n}.

Among the most natural and powerful methods to construct good expanders is the use of certain Cayley graphs of finitely generated groups (see [20, 23, 14]), via arguments related to Kazhdan’s property (T) (see [5]). Such graphs yield explicit constructions of expanders that have extremal spectral properties, namely Ramanujan graphs [20]. Being Cayley graphs of finitely generated groups, these constructions can be viewed as quotients of trees (Cayley graphs of free groups). It is natural to study hypergraph versions of this type of construction, based on quotients buildings (a type of higher dimensional simplicial complexes that extends the notion of a tree [33]). In particular, a notion of Ramanujan complex, which is a simplicial complex with extremal spectral properties analogous to Ramanujan graphs, was introduced and constructed in [3, 11, 19, 22, 21, 31]. Here we show that such constructions can yield highly overlapping bounded degree hypergraph families. Specifically, we show that for every integer r ⩾ 2, for a large enough odd prime power q, certain finite quotients of the building of P GL_{r}(F), where F is a non-archimedian local field with residue field of order q, are highly overlapping r-uniform hypergraphs (with degree and overlap number depending only q, r). Rather than defining the relevant notions in the introduction, we refer to Section 5 for precise definitions and statements. Instead, we state below the following concrete special case of our result, which follows from our argument in Section 5, in combination with a construction of Lubotzky, Samuels and Vishne [21].

3Gromov [17] calls such simplicial complexes “polyhedra with large cardinalities.”

Theorem 1.5. For every odd prime p and every integer r ⩾ 3 there exist k(p, r) ∈ ℕ and c(p, r) > 0 with the following property. For every m ∈ ℕ, the finite group G = P GL_{r}(𝔽_{p^{m}}), where 𝔽_{p^{m}} is the field of cardinality p^{m}, has a symmetric generating set S ⊆ G of size bounded above by k(p, r), such that the following holds. Consider the r-regular hypergraph H whose vertex set is G and whose hyperedges are those r-tuples {g_{1}, …, g_{r}} ⊆ G with g_{i}g_{j}^{−1} ∈ S for all distinct 1 ⩽ i, j ⩽ r (i.e., H is the hypergraph consisting of all cliques of size r in the Cayley graph induced by S). Then there exist arbitrarily large integers m for which the hypergraph H has overlap number at least c(p, r) > 0.

By Theorem 1.3, the best value of the constant c_{2} in Theorem 1.4 is close to \frac{2}{9}, but in higher dimensions d > 2, we do not have very good estimates for c_{d}. Our goal is to show, roughly speaking, that the best constant in Theorem 1.4 is the same as the best constant in the Boros-Füredi-Bárány theorem (Theorem 1.1). To state this formally, it will be convenient to introduce some notation. Let c(K_{n}^{d+1}) be the overlap number of K_{n}^{d+1}, the complete (d + 1)-uniform hypergraph on n vertices, and set

c(d) = lim_{n→∞} c (K_{n}^{d+1}) .

It is easy to show, via a straightforward point duplication argument, that the limit defining c(d) exists, and the Boros-Füredi-Bárány theorem shows that c(d) > 0, for every d.

One might suspect that if H is a (d + 1)-uniform hypergraph without isolated vertices, then c(H) ⩽ c(d) + o(1), where the o(1) term goes to 0 as the number of vertices of H tends to infinity. This is not the case. Consider, for example, the (d + 1)-hypergraph H_{n}^{d+1} on n vertices, whose hyperedges are those sets of size d + 1 that contain the first d vertices. In any general position embedding of the vertices of H_{n}^{d+1} in ℝ^{d}, any segment joining a pair of points sufficiently close and on opposite sides of the face consisting of the first d vertices stabs all the simplices induced by the images of hyperedges of H_{n}^{d+1}. Hence, c(H_{n}^{d+1}) ⩾ 1/2. However, c(d) decays to 0 at least exponentially in d (see, e.g., [4, 10]). Despite this example, we show that our suspicion is correct for bounded degree hypergraphs.

Theorem 1.6. For any d, Δ ∈ ℕ, and ε > 0, there is n(d, Δ, ε) ∈ ℕ such that every (d + 1)-uniform hypergraph H on n ⩾ n(d, Δ, ε) nonisolated vertices with maximum degree Δ satisfies c(H) ⩽ c(d) + ε.

In the other direction, we show that there are regular (d + 1)-uniform hypergraphs H of bounded degree such that c(H) is at least c(d) − ε for any given ε > 0.

Theorem 1.7. For each d ∈ ℕ and ε > 0, there is r(d, ε) ∈ ℕ such that for every r ⩾ r(d, ε) and sufficiently large n which is a multiple of d + 1, there is a (d + 1)-uniform, r-regular hypergraph H on n vertices with c(H) ⩾ c(d) − ε.

The previous two theorems essentially show that c(d) is the largest possible overlap number for bounded degree hypergraphs with sufficiently many nonisolated vertices.

The proof of the last theorem is based on a geometric partitioning result of independent interest. A (d + 1)-tuple of subsets S_{1}, …, S_{d+1} ⊆ ℝ^{d} is said to be homogeneous with respect to a point q ∈ ℝ^{d} if either all simplices with one vertex in each of the sets S_{1}, …, S_{d+1} contain q, or none of these simplices contain q.

Theorem 1.8. For a positive integer d and ε > 0, there exists another positive integer K = K(ε, d) ⩾ d + 1 such that for any k ⩾ K the following statement is true. 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} = A_{1} ∪ … ∪ A_{k} into k measurable parts of equal measure such that all but at most an ε-fraction of the (d + 1)-tuples A_{i_{1}}, …, A_{i_{d+1}} are homogenous with respect to q.

An equipartition of a finite set is a partition of the set into subsets whose sizes differ by at most one. A discrete version of Theorem 1.8 is the following.

Corollary 1.9. Given a positive integer d and ε > 0, there exists another positive integer K = K(ε, d) ⩾ d + 1 such that for any k ⩾ K the following statement is true. For any finite set P ⊆ ℝ^{d} and for any point q ∈ ℝ^{d}, there is an equipartition P = P_{1} ∪ … ∪ P_{k} such that all but at most an ε-fraction of the (d + 1)-tuples P_{i_{1}}, …, P_{i_{d+1}} are homogenous with respect to q.

Notice that due to Bárány’s result [4] that c(d) > 0, by taking ε ≪ c(d), Corollary 1.9 immediately implies Theorem 1.2.

The rest of the paper is organized as follows. Section 2 contains a detailed topological proof of the Boros-Füredi theorem (Theorem 1.1), following Gromov’s approach in [17]. In the two subsections of Section 3, we present randomized constructions for Theorems 1.3 and 1.4. In the plane, these constructions are nearly optimal; their overlap numbers are close to the value \frac{2}{9}. In Section 4, we give a deterministic recipe how to turn certain families of explicitly given expander graphs into families of highly overlapping (d + 1)-uniform hypergraphs. In Section 5 we give a criterion which ensures that certain finite quotients of the building of P GL_{r}(F) are highly overlapping r-uniform hypergraphs; this criterion implies in particular Theorem 1.5. In Section 6, we establish a Szemerédi-type theorem for infinite hypergraphs with a measure on their vertex sets (Theorem 6.1). This is used in Section 7 for the proof of the geometric partition result Theorem 1.8. In Section 8, we show how this result can be applied to obtain Theorem 1.7. Section 9 contains the proof of Theorem 1.6.

For the sake of clarity of the presentation, in the rest of this paper, we systematically omit floor and ceiling signs whenever they are not crucial. We shall also assume throughout that all embeddings of hypergraphs into ℝ^{d} are such that the vertices are mapped to points in general position. Even though the corresponding statements for degenerate embeddings will then follow from standard limiting arguments, it is convenient to make this assumption in order to not deal explicitly with such degeneracies in each of the proofs.

2. A topological proof of the Boros-Füredi theorem

We will prove a somewhat stronger statement. Given a set P of n points in the plane, a ray (closed half-line) is said to be exposed if it has nonempty intersection with fewer than n^{2}/9 segments connecting point pairs in P. The set of all segments connecting two elements of P forms a complete geometric graph K(P) on the vertex set P, and we refer to these segments as the edges of K(P).

Proposition 2.1. Given a set P of n points in the plane, one can always find a point q not necessarily in P such that no ray emanating from q is exposed.

Suppose that such a point q does not belong to P. For each p ∈ P, ray emanating from q in the direction opposite to p intersects at least n^{2}/9 edges of K(P). Each such edge, together with p, spans a triangle that contains q. Every triangle is counted at most three times, therefore the total number of triangles containing q is at least n(n^{2}/9)/3 = n^{3}/27. If q belongs to P, the number of (closed) triangles containing q is larger than n^{3}/27.

Thus, it is sufficient to prove Proposition 2.1. Suppose for a contradiction that for each point q of the plane, there is an exposed ray emanating from q. Let D denote a large disk around the origin O, which contains all elements of P, and let S^{1} denote the boundary of D. For σ ∈ ℝ^{2} \ {O}, we denote by ray(q, σ) the ray emanating from q in the direction parallel to \overrightarrow{Oσ}.

Notice that for any two exposed rays, ray(q, σ) and ray(q, τ), emanating from the same point, one of the two closed regions bounded by them contains fewer than n/3 points of P. Otherwise, one of the regions has x points of P with n/3 ⩽ x ⩽ 2n/3, and the two boundary rays together would intersect at least x(n − x) ⩾ (n/3)(2n/3) = 2n^{2}/9 edges, which implies at least one of them was not exposed.

Let I denote the set of all pairs (q, ϱ) ∈ D×S^{1}, for which ray(q, ϱ) is exposed or belongs to the closed region bounded by two exposed rays, ray(q, σ) and ray(q, τ), that contains fewer than n/3 points of P.

Claim 2.2. The set I has the following properties:

(a) I is an open subset of D × S^{1},

(b) (ϱ, ϱ) ∈ I for all ϱ ∈ S^{1},

(c) for every q ∈ D, the set I_{q} =^{def} {ϱ ∈ S^{1} : (q, ϱ) ∈ I} is a nonempty proper subinterval of S^{1}.

Proof. Parts (a) and (b) directly follow from the definition. It is also clear, by our contrapositive assumption, that I_{q} is a nonempty interval for every q ∈ D.

We have to show only that I_{q} ≠ S^{1}. To see this, let ray(q, ϱ) be an exposed ray emanating from q, and let ϱ′ ∈ S^{1} be a direction such that both closed regions bounded by ray(q, ϱ) and ray(q, ϱ′) contain at least n/2 points of P.

We claim that ϱ′ ∉ I_{q}. Otherwise, we can select two exposed rays, ray(q, σ) and ray(q, τ), such that ray(q, ϱ′) belongs to the closed region bounded by them which contains fewer than n/3 points. The three rays, ray(q, ϱ), ray(q, σ), and ray(q, τ), cut the plane into three closed regions, and it is easy to see that each of them must contain fewer than n/3 points, which is a contradiction. Indeed, if e.g. the region bounded by ray(q, ϱ) and ray(q, σ) that does not contain ray(q, τ) had at least n/3 points, then by the discussion above the closure of its complement had fewer than n/3 points, contradicting our assumption that both closed regions bounded ray(q, ϱ) and ray(q, ϱ′) contain at least n/2 points. □

Now we can obtain the desired contradiction, thus completing the proof of Proposition 2.1, by applying to J =^{def} (D × S^{1}) \ I the following version of the Brouwer fixed point theorem.

Lemma 2.3. Let J be a closed subset of D × S^{1} with the property that for every q ∈ D we have that J_{q} =^{def} {ϱ ∈ S^{1} : (q, ϱ) ∈ J} is a nonempty proper (closed) subinterval of S^{1}. Then (ϱ, ϱ) ∈ J, for some ϱ ∈ S^{1}.

To see why Lemma 2.3 holds true, assume for contradiction that (ϱ, ϱ) ∉ J, for all ϱ ∈ S^{1}. Write J_{S} =^{def} J ∩ (S^{1} × S^{1}), and let P roj_{1}, P roj_{2} : J_{S} → S^{1} denote the projections onto the first and second coordinates, respectively. The fibers of P roj_{1} are nonempty proper closed intervals, and therefore P roj_{1} induces a bijection between π_{1}(J_{S}) and π_{1}(S^{1}) = ℤ. But, the contrapositive assumption implies that P roj_{1} and P roj_{2} are homotopic, and therefore P roj_{2} also induces a bijection between π_{1}(J_{S}) and π_{1}(S^{1}). This is a contradiction since P roj_{2} extends to J, and π_{1}(J) = 0 since J is fibered over D with fibers equal to intervals.

Clearly, Lemma 2.3 contradicts part (b) of Claim 2.2. □

3. Sparse constructions using the probabilistic method

In this section, we prove Theorems 1.3 and 1.4 using the probabilistic method. Our planar construction is nearly optimal, but in higher dimensions the overlap numbers of our hypergraphs will be far from maximal. We note that our proofs use a non-uniformly random choice of (d + 1)-uniform hypergraphs of degree k_{d}, which is designed especially for our purposes. Nevertheless, the argument in Section 8, which uses Theorem 1.8, shows that assuming the degree r satisfies a large enough lower bound depending on d (which is inferior to the bound on k_{d} obtained in this section), for a hypergraph H chosen uniformly at random among all (d + 1)-uniform hypergraphs of degree r, with high probability c(H) will be bounded below by a positive constant depending only on d (which is also inferior to the bound on c_{d} obtained in this section).

3.1. Highly overlapping triple systems—Proof of Theorem 1.3. The outline of the proof of Theorem 1.3 is the following. We first pick t randomly and independently selected partitions of the set [n] = {1, 2, …, n} into parts of equal size b. We define H_{n} to be the 3-uniform hypergraph with vertex set [n], consisting of all triples that lie in the same part in at least one of the t partitions. Finally, we will show that H_{n} meets the requirements of Theorem 1.3.

We need the following simple technical lemma. A key ingredient that is used in the proof is the Chernoff bound for negatively associated random variables (see, e.g., [15]). It implies that if A_{1}, …, A_{n} are n mutually negatively correlated events in an arbitrary probability space such that A_{i} has probability p_{i}, then the probability that the number of A_{i} which occur exceeds the expected number p_{1} + ⋯ + p_{n} by at least a is at most e^{−2a^{2}/n}.

Lemma 3.1. Suppose that δ > 0, and let b = δ^{−3}, β = 2e^{−2δ^{2}b}, r = 4β^{−2}b, t = rδ^{−1}. If n is a sufficiently large multiple of b, then there exist t partitions P_{1}, …, P_{t} of [n], each consisting of n/b parts of size b, with the following two properties:

(1) any two parts of size b in different partitions have at most two elements in common,

(2) for every subset S ⊆ [n], there are fewer than r partitions P_{i} for which at least βn/b parts contain at least (\frac{|S|}{n} + δ) b elements of S.

Proof. We verify that t randomly selected partitions of [n] into parts of equal size b almost surely have the desired properties. Fix a set S ⊆ [n], and consider a random partition P of [n] into parts I_{1}, …, I_{n/b} of size b. For any 1 ⩽ i ⩽ n/b, let A_{i} denote the event that |I_{i} ∩ S| ⩾ (\frac{|S|}{n} + δ) b. For any 1 ⩽ j ⩽ b, let A_{i,j} denote the event that the jth element of I_{i} is in S. The events A_{i,1}, …, A_{i,b} are mutually negatively correlated and each of them has probability |S|/n. Thus, by Chernoff’s bound [15], we have

Pr[A_{i}] ⩽ e^{−2(δb)^{2}/b} = e^{−2δ^{2}b} = \frac{β}{2} .

Let X denote the event that at least βn/b of the events A_{1}, …, A_{n/b} occur. Since the events A_{1}, …, A_{n/b} are also mutually negatively correlated and each has probability at most β/2, we can again apply the Chernoff bound [15] to obtain

Pr[X] ⩽ e^{−2( \frac{βn}{2b})^{2}/(n/b)} = e^{− \frac{1}{2} β^{2}n/b}.

Take t independent random partitions of [n], P_{1}, …, P_{t}, each consisting of n/b parts of size b. The probability that a given pair of parts of size b have at least 3 elements in common is at most \binom{b}{3} (\frac{b}{n})^{3} ⩽ \frac{b^{6}}{6n^{3}} . Since there are \binom{tn/b}{2} such pairs, by linearity of expectation, the probability that there is a pair sharing at least 3 elements is at most \binom{tn/b}{2} \frac{b^{6}}{6n^{3}} < \frac{t^{2}b^{4}}{12n}. Hence, by our choice of parameters, almost surely condition (1) will be satisfied.

For a fixed S ⊆ [n], the probability that for at least r of the partitions P_{1}, …, P_{t}, at least βn/b of the b-element subsets of the partition have at least (\frac{|S|}{n} + δ) b elements in S is at most

\binom{t}{r}(Pr[X])^{r} ⩽ \binom{t}{r}e^{−r \frac{1}{2} β^{2}n/b} = \binom{t}{r}e^{−2n} ⩽ e^{−n}.

The number of subsets S of [n] is 2^{n}. Hence, by linearity of expectation, the expected number of subsets S with property (2) is o(1). We conclude that there are t such partitions with the desired properties. □

Let δ = ε/50 and k = t\binom{b−1}{2}. Consider the 3-uniform hypergraph H_{n} with V (H_{n}) = [n], the hyperedges of which are those triples that lie in the same part in at least one (hence, precisely one) of the partitions P_{1}, …, P_{t} meeting the requirements of Lemma 3.1. Clearly, in H_{n}, each vertex belongs to k = t\binom{b−1}{2} hyperedges.

The proof of Theorem 1.3 can now be completed by adapting the idea of Bukh [9]. Consider an embedding of the vertices of H_{n} in the plane. We shall use the following lemma of Ceder [13]:

Lemma 3.2 (Ceder [13]). Assume that n is divisible by 6. Given any set of n points in the plane, there are three concurrent lines that divide the plane into 6 angular regions, each containing roughly the same number of points. More precisely, there are disjoint \frac{n}{6}-element point sets S_{1}, …, S_{6} such that S_{i} is contained in the closure of region i.

We shall assume throughout the n is divisible by 6. Let S_{1}, …, S_{6} be the sets from Lemma 3.2, and let p denote the intersection point of the three lines from Lemma 3.2. By a simple case analysis, Bukh [9] showed that, for every choice of six points, one from each S_{i}, at least 8 of the \binom{6}{3} = 20 triangles induced by them contain p.

Let I ⊆ [n] be a b-element set such that |I ∩ S_{i}| ⩽ (\frac{|S_{i}|}{n} + δ)b = (1 + 6δ)\frac{b}{6}, for 1 ⩽ i ⩽ 6. Obviously, we have

|I ∩ S_{i}| ⩾ b − 5(1 + 6δ)\frac{b}{6} ⩾ (1 − 30δ)\frac{b}{6},

for every i. Each of the

∏_{i=1}^{6} |I ∩ S_{i}| ⩾ (1 − 30δ)^{6} (\frac{b}{6})^{6}

6-element sets with one vertex from each I ∩S_{i} induces at least 8 triangles that contain point p. Each of these triangles belongs to at most (1 + 6δ)^{3}(\frac{b}{6})^{3} such 6-element sets. Thus, there are at least

8\frac{(1 − 30δ)^{6} (\frac{b}{6})^{6}}{(1 + 6δ)^{3}(\frac{b}{6})^{3}} ⩾ \frac{1}{27}(1 − 200δ)b^{3} > (1 − 200δ)\frac{2}{9}\binom{b}{3}

triangles induced by three vertices in I which contain p.

According to part 2 of Lemma 3.1, for every i, 1 ⩽ i ⩽ 6, fewer than r partitions P_{j} have the property that at least β \frac{n}{b} of their parts contain at least (1 + 6δ)\frac{b}{6} elements of S_{i}. Hence, the total number of b-element parts I in all t partitions, for which |I ∩ S_{i}| > (1 + 6δ)\frac{b}{6} for some i, 1 ⩽ i ⩽ 6, is smaller than

6r\frac{n}{b} + 6tβ \frac{n}{b} = 6δt\frac{n}{b} + 6βt\frac{n}{b} ⩽ 10δt\frac{n}{b}.

It follows that the fraction of the t\frac{n}{b} \binom{b}{3} hyperedges of H_{n} that contain point p in this embedding is at least

(1 − 10δ)(1 − 200δ)\frac{2}{9} ⩾ (1 − 210δ)\frac{2}{9} ⩾ \frac{2}{9} − ε,

which completes the proof of Theorem 1.3. □

3.2. Higher dimensions—Proof of Theorem 1.4. As in the proof of Theorem 1.3, we establish Theorem 1.4 using Lemma 3.1. We may assume that c′_{d} = 1/m with m an integer, where c′_{d} is the constant in Theorem 1.2, and let n be a multiple of m. Set δ = \frac{1}{2m(m−1)} and apply Lemma 3.1. Consider now the (d + 1)-uniform hypergraph H_{n} with V (H_{n}) = [n], the hyperedges of which are those (d + 1)-element sets that lie in the same part in at least one (hence, precisely one) of the partitions P_{1}, …, P_{t} meeting the requirements of Lemma 3.1. Clearly, in H_{n}, each vertex belongs to k_{d} = t\binom{b−1}{d} hyperedges.

Consider now any embedding of V (H_{n}) into ℝ^{d}, and let P denote the image of V (H_{n}). By Theorem 1.2, one can find disjoint c′_{d}n-element subsets P_{1}, P_{2}, …, P_{d+1} ⊆ P and a point q such that picking one element from each subset P_{i}, their convex hull always contains q. We extend this to a partition P = P_{1} ∪ … ∪ P_{m} into subsets of size n/m by picking the P_{i} for d + 1 < i ⩽ m of size n/m arbitrarily.

Let I ⊆ [n] be a b-element set such that

∀1 ⩽ i ⩽ m, |I ∩ P_{i}| ⩽ (\frac{|P_{i}|}{n} + δ) b = (1 + \frac{1}{2(m − 1)}) \frac{b}{m}.

Obviously, we have

|I ∩ P_{i}| ⩾ b − (m − 1) (1 + \frac{1}{2(m − 1)}) \frac{b}{m} = \frac{b}{2m},

for every 1 ⩽ i ⩽ m. Each of the

∏_{i=1}^{d+1} |I ∩ P_{i}| ⩾ (\frac{b}{2m})^{d+1}

(d + 1)-element sets with one vertex from each I ∩ P_{1}, …, I ∩ P_{d+1} induces a closed simplex containing point q. Hence, the fraction of (d + 1)-element subsets of I which induce a closed simplex that contains point q is at least

(\frac{b}{2m})^{d+1} \binom{b}{d + 1}^{−1} ⩾ (d + 1)! (\frac{c′_{d}}{2} )^{d+1} .

According to part (2) of Lemma 3.1, for every 1 ⩽ i ⩽ m, fewer than r partitions P_{j} have the property that at least β \frac{n}{b} of their parts contain at least (\frac{|P_{i}|}{n} + δ)b elements of P_{i}. Hence, the total number of b-element parts I in all t partitions, for which |I ∩ P_{i}| > (\frac{|P_{i}|}{n} + δ)b for some 1 ⩽ i ⩽ m, is smaller than

mr\frac{n}{b} + mtβ \frac{n}{b} = mδt\frac{n}{b} + mβt\frac{n}{b} ⩽ \frac{3}{4} · t · \frac{n}{b}.

Hence, the fraction of the t\frac{n}{b} \binom{b}{d+1} hyperedges of H_{n} that contain the point q in this embedding

is at least \frac{1}{4}(d + 1)! (\frac{c′_{d}}{2} )^{d+1}. □

4. Deterministic constructions using expander graphs

In the next two subsections, we present deterministic constructions based on expander graphs, to provide alternative proofs of Theorem 1.3 and Theorem 1.4. These proofs yield significantly better bounds on k(ε) and k_{d} in Theorem 1.3 and Theorem 1.4, respectively.

As in the previous section, the proof gives a nearly optimal bound in the plane, but not in higher dimension.

4.1. Highly overlapping triple systems—second proof of Theorem 1.3. Fix integers k, n ∈ ℕ, with n divisible by 6, and let G = ({1, …, n}, E) be a k-regular graph on the vertex set {1, …, n}. Let k = λ_{1} ⩾ λ_{2} ⩾ ⋯ ⩾ λ_{n} be the eigenvalues of the adjacency matrix of G in decreasing order, and write λ = max_{i∈{2,...,n}} |λ_{i}|. For any S, T ⊆ {1, …, n} let E(S, T) denote the number of ordered pairs (i, j) ∈ S × T such that ij ∈ E. The expander mixing lemma (see Corollary 9.2.5 in [1]) states that

|E(S, T) − \frac{k|S| · |T |}{n}| ⩽ λ\sqrt{|S| · |T |}.  (1)

For every i ∈ {1, …, n} let N_{G}(i) =^{def} {j ∈ {1, …, n} : ij ∈ E} denote its neighborhood in G. Define a hypergraph H on the vertex set {1, …, n} by letting E(H) consist of those triples {i, j, ℓ} for which there exists r ∈ {1, …, n} such that ir, jr, ℓr ∈ E, i.e., i, j, ℓ ∈ N_{G}(r). Assume from now on that the graph G is quadrilateral-free. This implies that the hyperedges in H corresponding to three vertices i, j, ℓ ∈ N_{G}(r) cannot arise from neighborhoods of vertices of G other than r itself. Hence the 3-uniform hypergraph corresponding to H is k\binom{k−1}{2}-regular and |E(H)| = \binom{k}{3}n.

Fix ε, δ ∈ (0, 1). Let \{P_{i}\}_{i=1}^{6} be a partition of \{1, …, n\} such that |P_{j}| = \frac{n}{6} for all 1 ⩽ j ⩽ 6. Write

A_{j} = \{i ∈ \{1, …, n\} : |N_{G}(i) ∩ P_{j}| < \frac{(1 − δ)k}{6} \} .

Then, by definition, we have E(A_{j}, P_{j}) < |A_{j}|\frac{(1−δ)k}{6}. An application of (1) yields the inequality:

|A_{j}|\frac{(1 − δ)k}{6} ⩾ \frac{k|A_{j}| · |P_{j}|}{n} − λ\sqrt{|A_{j}| · |P_{j}|} = \frac{k|A_{j}|}{6} − λ\sqrt{\frac{n|A_{j}|}{6}},

which simplifies to

|A_{j}| ⩽ \frac{6λ^{2}n}{δ^{2}k^{2}}.

Thus, if we define

A = \{i ∈ \{1, …, n\} : |N_{G}(i) ∩ P_{j}| ⩾ \frac{(1 − δ)k}{6} ∀j ∈ \{1, …, 6\}\} ,  (2)

then

A ⩾ n − ∑_{j=1}^{6} |A_{j}| ⩾ n (1 − \frac{36λ^{2}}{δ^{2}k^{2}} ) .  (3)

We shall assume from now on that \frac{36λ^{2}}{δ^{2}k^{2}} < 1. We also note that for every i ∈ A and j ∈ {1, …, 6} we have

|N_{G}(i) ∩ P_{j}| ⩽ k − ∑_{r∈\{1,...,6\}\\{j\}} |N_{G}(i) ∩ P_{r}| ⩽ k − 5\frac{(1 − δ)k}{6} = \frac{(1 + 5δ)k}{6} .  (4)

Let x_{1}, …, x_{n} ∈ ℝ^{2} be an embedding of {1, …, n} in the plane. Let S_{1}, …, S_{6} be a partition of {x_{1}, …, x_{n}}, as in the first proof of Theorem 1.3, which corresponds to the three concurrent lines from Lemma 3.2, whose common intersection point is p ∈ ℝ^{2}. We shall use the above reasoning (and notation) for the partition P_{1}, …, P_{6} of {1, …, n} given by P_{j} = {i ∈ {1, …, n} : x_{i} ∈ S_{i}}.

Fix i ∈ A, where A is as in (2). For every (j_{1}, …, j_{6}) ∈ ∏_{r=1}^{6}(N_{G}(i) ∩ P_{r}) at least 8 of the 20 triangles induced by the points {x_{j_{1}}, …, x_{j_{6}}} contain p. By the definition of A, there

are at least (\frac{(1−δ)k}{6})^{6} such 6-tuples, while, using (4), each of these triangles that contains p

belongs to at most (\frac{(1+5δ)k}{6})^{3} such 6-tuples. Observe also that by the definition of H, since all of these triangles correspond to neighbors of i, their corresponding triples of indices belong to E(H), and since G is quadrilateral-free, they cannot arise from the above reasoning with i replaced by any other vertex. Thus, the number of triangles that are images of hyperedges of H and contain p is at least

8 · \begin{matrix}(\frac{(1−δ)k}{6}) & 6 \\ (\frac{(1+5δ)k}{6}) & 3 \end{matrix} · |A| ⩾^{(3)} \frac{(1 − δ)^{6}k^{3}}{27(1 + 5δ)^{3}} n (1 − \frac{36λ^{2}}{δ^{2}k^{2}} ) = (1 − O (δ + \frac{λ^{2}}{δ^{2}k^{2}} + \frac{1}{k})) · \frac{2}{9}\binom{k}{3}n. (5)

For arbitrarily large n, we can choose the graph G so that it is quadrilateral-free and λ ⩽ 2\sqrt{k} (e.g., Ramanujan graphs work—see [20, 18]). By choosing δ ≍ ε and k ≍ \frac{1}{ε^{3}} in (5), we get that p is in at least (\frac{2}{9} − ε) |E(H)| of the triangles in that are images of hyperedges of H. Note that the degree of H is O(k^{3}) = O (\frac{1}{ε^{9}} ). This proves Theorem 1.3 with the bound k(ε) = O (\frac{1}{ε^{9}} ). □

4.2. Higher dimensions—second proof of Theorem 1.4. Here we shall use a variant of the construction in Section 4.1, to give an alternative proof of Theorem 1.4. We use the notation from Section 4.1, and we assume that k ⩾ d. Fix n vectors x_{1}, …, x_{n} ∈ ℝ^{d}. Define a set of d-dimensional simplices H′ whose vertices are in {x_{1}, …, x_{n}} by taking the simplex whose vertices are the distinct vectors {x_{j_{1}}, x_{j_{2}}, …, x_{j_{d+1}}} if and only if we have j_{1}j_{2}, j_{2}j_{3}, … j_{d}j_{d+1} ∈ E. In other words, the simplices in H′ correspond to non-returning walks of length d in G. Thus, |H′| ⩽ k^{d}n.

Let P_{1}, …, P_{d+1} ⊆ {x_{1}, …, x_{n}} be the disjoint subsets from Theorem 1.2, i.e., |P_{i}| ⩾ c′_{d}n, and all the closed simplices with one vertex in each of the sets {P_{1}, …, P_{d+1}} have a point in common. Set Q_{i} = {j ∈ {1, …, n} : x_{j} ∈ P_{i}}. Define Q̃_{d+1} = Q_{d+1} and inductively for i ∈ {2, …, d + 1},

Q̃_{i−1} = {j ∈ Q_{i−1} : ∃ℓ ∈ Q̃_{i} jℓ ∈ E} .

Then, by definition, there are no edges between Q_{i−1} \ Q̃_{i−1} and Q̃_{i}. It follows from (1) that

\frac{k}{n} |Q_{i−1} \ Q̃_{i−1}| · |Q̃_{i}| ⩽ λ\sqrt{|Q_{i−1} \ Q̃_{i−1}| · |Q̃_{i}|}.

Thus, we have

\frac{λ^{2}n^{2}}{k^{2}} ⩾ (|Q_{i−1}| − |Q̃_{i−1}|) |Q̃_{i}| ⩾ (c′_{d}n − |Q̃_{i−1}|) |Q̃_{i}| ,

or

|Q̃_{i−1}| ⩾ c′_{d}n − \frac{λ^{2}n^{2}}{k^{2} |Q̃_{i}|}.  (6)

Assuming that λ ⩽ \frac{c′_{d}}{2} k, inequality (6) implies by induction that for all i ∈ \{1, …, d+1\} we have |Q̃_{i−1}| ⩾ \frac{c′_{d}}{2} n (for i = d + 1 this follows from our assumption, arising from Theorem 1.2,

on the cardinality of P_{d+1}). Thus, |Q̃_{1}| ⩾ \frac{c′_{d}}{2} n, and by construction any point j ∈ Q̃_{1} can be completed to a walk in G of length d whose ith vertex is in Q_{i}. Each such walk corresponds to a simplex in H′, and by Theorem 1.2, all of these simplices have a common point. Thus, the number of simplices in H′ which have a common point is at least \frac{c′_{d}}{2} n ⩾ \frac{c′_{d}}{2k^{d}} |H′|. Since there exist arbitrarily large graphs G with λ ⩽ \frac{c′_{d}}{2} k and k ⩽ k_{d} (e.g., for Ramanujan graphs we can take k_{d} ≍ \frac{1}{(c′_{d})^{2}} ), this completes our deterministic proof of Theorem 1.4. □

5. Finite quotients of buildings

Let F be a non-archimedean local field, O_{F} its ring of integers, π_{F} a uniformizer and q = |O_{F} /π_{F} O_{F} | the cardinality of the residue field of F. For example, we may take F = ℚ_{p}, O_{F} = ℤ_{p}, π_{F} = p and q = p. We assume below that q is odd.

Let r ⩾ 3 be an integer and G = P GL_{r}(F). Now r is fixed but F will be chosen such that q is big enough. We recall that K = P GL_{r}(O_{F}) is a maximal compact subgroup of G. We also recall that G/K is the set of vertices of a building, and is also equal to the set of lattices in F^{r} up to homothety (a lattice in F^{r} is a free O_{F} -submodule of rank r and a homothety is the multiplication by an element of the multiplicative group F^{×}). We refer to [33] for an elementary introduction to the building of P GL_{r}(F) (we will not use the definition of a building below—all simplicial complexes will be defined explicitly). We have the map

type : G/K → ℤ/rℤ

such that if x ∈ G/K is the homothety class of a lattice M ⊆ F^{r} and det(M) = π_{F}^{a} O_{F}^{×} with a ∈ ℤ, then type(x) = a mod rℤ. We denote by vdet(·) the composition

G ⟶^{det} F^{×}/(F^{×})^{r} ⟶^{valuation} ℤ/rℤ,

and for i ∈ ℤ/rℤ we write G_{i} = vdet^{−1}({i}). Thus, G_{0} is a subgroup of index r in G and the G_{i} are the left and right cosets for G_{0} in G. We remark that K ⊆ G_{0}. For g ∈ G_{i} and x ∈ G/K we have type(gx) = i + type(x). Moreover, G_{i}/K is the subset of G/K of vertices of type i.

Let Λ = {(λ_{1}, ..., λ_{r}) ∈ ℤ^{r}/ℤ(1, ..., 1) : λ_{1} ⩽ ... ⩽ λ_{r}} be the set of dominant coweights of P GL_{r}(F). For (λ_{1}, ..., λ_{r}) ∈ Λ we write

D(λ_{1}, ..., λ_{r}) = (\begin{matrix}π_{F}^{λ_{1}} & 0 & … & … & 0 \\ 0 & π_{F}^{λ_{2}} & ... & ... & ⋮ \\ ⋮ & ... & π_{F}^{λ_{3}} & ... & ⋮ \\ ⋮ & ... & ... & ... & 0 \\ 0 & … & … & 0 & π_{F}^{λ_{r}} \end{matrix} ) ∈ G.

Then the mapping δ =^{def} (λ_{1}, ..., λ_{r}) ↦ KD(λ_{1}, ..., λ_{r})K is a bijection from Λ to K\G/K. For x, y ∈ G/K we have x^{−1}y ∈ K\G/K, and we define the relative position of x and y in the building as σ(x, y) = δ^{−1}(x^{−1}y) ∈ Λ. In other words, for (λ_{1}, ..., λ_{r}) ∈ Λ we have σ(x, y) = (λ_{1}, ..., λ_{r}) if and only if there exists a basis (e_{1}, ..., e_{r}) of F^{r} such that x is the homothety class of O_{F} e_{1} +...+O_{F} e_{r} and y is the homothety class of π_{F}^{λ_{1}}O_{F} e_{1} +...+π_{F}^{λ_{r}}O_{F} e_{r}. The inverse image of K\G_{0}/K under δ is

Λ_{0} = {(λ_{1}, ..., λ_{r}) ∈ ℤ^{r}/ℤ(1, ..., 1) : λ_{1} ⩽ ... ⩽ λ_{r} ∧ ∑_{i=1}^{r} λ_{i} = 0 in ℤ/rℤ} ⊆ Λ,

which is also the set of dominant coweights of SL_{r}(F).

We recall that for d ∈ {0, ..., r − 1} a d-dimensional face of the building is a (d + 1)-tuple {y_{0}, ..., y_{d}} ⊆ G/K such that there are lattices M_{0}, ..., M_{d} in F^{r} satisfying

(1) M_{0} ⊊ M_{1} ⊊ ... ⊊ M_{d} ⊊ π_{F}^{−1}M_{0},

(2) y_{0}, ..., y_{d} are the homothety classes of M_{0}, ..., M_{d}.

The type of a face {y_{0}, ..., y_{d}} is {type(y_{0}), ..., type(y_{d})} ⊆ ℤ/rℤ. For any non-empty subset I ⊆ ℤ/rℤ we denote by Y_{I} the set of faces of type I in the building. More precisely, we denote by Y_{I} the set of families (y_{i})_{i∈I} with y_{i} ∈ G_{i}/K such that {y_{i} : i ∈ I} is a (|I| − 1)-dimensional face of the building.

Let G^{+} ⊆ G be the subgroup generated by unipotent elements of G. Then G^{+} is also the image of SL_{r}(F) in G = P GL_{r}(F), and G^{+} ⊆ G_{0}. We have an exact sequence

1 → G^{+} → G ⟶^{det} F^{×}/(F^{×})^{r} → 1.

We will apply Theorem 1.1 of [26] (a quantitative form of Kazhdan’s property (T)) to the strongly orthogonal system of the set of roots of G = P GL_{r}(F) consisting of the single root e_{1} −e_{r} (where e_{i} −e_{j} stands for the root corresponding to the character of the maximal torus of diagonal matrices which sends D(λ_{1}, ..., λ_{r}) ∈ G to π_{F}^{λ_{i}−λ_{j}}, for (λ_{1}, ..., λ_{r}) ∈ Λ). By this theorem, for any unitary representation (H, π) of G without a nonzero G^{+}-invariant vector, for any (λ_{1}, ..., λ_{r}) ∈ Λ and for any K-invariant vectors ξ, η ∈ H we have

|⟨η, π(D(λ_{1}, ..., λ_{r}))ξ⟩| ⩽ \frac{(λ_{r} − λ_{1})(q − 1) + (q + 1)}{q^{\frac{1}{2} (λ_{r}−λ_{1})}(q + 1)}∥ξ∥ · ∥η∥.  (7)

For any nonzero (λ_{1}, ..., λ_{r}) ∈ Λ_{0} we have λ_{r} ⩾ λ_{1} + 2 and therefore inequality (7) implies

|⟨η, π(D(λ_{1}, ..., λ_{r}))ξ⟩| ⩽ \frac{3}{q}∥ξ∥ · ∥η∥ for any nonzero (λ_{1}, ..., λ_{r}) ∈ Λ_{0}.  (8)

Note that in (7) we did not use the full strength of Theorem 1.1 of [26] because we used the very poor strongly orthogonal system {e_{1} − e_{r}}, whereas [26] uses the maximal strongly orthogonal system \{e_{1} − e_{r}, e_{2} − e_{r−1}, ..., e_{⌊ \frac{r}{2} ⌋} − e_{r+1−⌊ \frac{r}{2} ⌋}\} to get optimal bounds. However, the optimal bounds do not give in (8) an exponent of q better than −1 for (λ_{1}, ..., λ_{r}) = (−1, 0, ..., 0, 1).

Let Γ be a cocompact lattice in G_{0} satisfying the condition

(C) for any x ∈ G/K and any γ ∈ Γ different from 1, the distance from x to γx along the 1-skeleton of G/K is > 2.

The quotient X = Γ\G/K is the set of vertices of a simplicial complex whose faces are the quotient by Γ of the faces of the building G/K. Since Γ ⊆ G_{0}, we have an obvious type function type : X → ℤ/rℤ, and thanks to the condition (C), X has no multiple edges. For any non-empty subset I ⊆ ℤ/rℤ we write X_{I} = Γ\Y_{I} and we identify X_{I} with the set of faces of type I in X. We note that for i ∈ ℤ/rℤ, X_{{i}} =^{def} Γ\G_{i}/K is the subset of vertices of type i in X and is of cardinality \frac{1}{r}|X|.

For any (λ_{1}, ..., λ_{r}) ∈ Λ we have a normalized Hecke operator H_{λ_{1},...,λ_{r}} acting on ℓ^{2}(Γ\G/K) in the following way: we view elements of ℓ^{2}(Γ\G/K) as Γ-invariant functions on G/K and H_{λ_{1},...,λ_{r}}(f)(x) is the average of the values of f on the vertices y ∈ G/K which satisfy σ(x, y) = (λ_{1}, ..., λ_{r}). For ξ, η ∈ ℓ^{2}(Γ\G/K) considered as K-invariants vectors in L^{2}(Γ\G), endowed with the representation π of G by right translations, we have

⟨η, H_{λ_{1},...,λ_{r}}ξ⟩ = ⟨η, π(D(λ_{1}, ..., λ_{r}))ξ⟩.  (9)

The subspace of G^{+}-invariant vectors in L^{2}(Γ\G) is L^{2}(Γ\G)^{G^{+}} = L^{2}(F^{×}/(F^{×})^{r} det(Γ)) because G/G^{+} = F^{×}/(F^{×})^{r} is abelian. Let H be the orthogonal complement of L^{2}(Γ\G)^{G^{+}} in L^{2}(Γ\G). The representation (H, π) does not have any nonzero G^{+}-invariant vector and we will apply inequality (8) to it. For any set Z endowed with a finite measure we write L_{0}^{2}(Z) for the hyperplane of L^{2}(Z) which is orthogonal to the constant function 1. For (λ_{1}, ..., λ_{r}) ∈ Λ_{0}, H_{λ_{1},...,λ_{r}} acts diagonally on the direct sum decomposition ℓ^{2}(Γ\G/K) = ⨁_{i∈ℤ/rℤ} ℓ^{2}(Γ\G_{i}/K) and the estimate (8), together with (9), implies the operator norm bound

∥H_{λ_{1},...,λ_{r}}∥_{L(ℓ_{0}^{2}(Γ\G_{i}/K))} ⩽ \frac{3}{q},  (10)

for any i ∈ ℤ/rℤ and for any nonzero (λ_{1}, ..., λ_{r}) ∈ Λ_{0}. To justify (10) it remains to check that for any i ∈ ℤ/rℤ and any f ∈ ℓ_{0}^{2} (Γ\G_{i}/K), the extension of f by 0 to Γ\G/K, considered as an element of L^{2}(Γ\G), belongs to H, i.e., is orthogonal to L^{2}(Γ\G)^{G^{+}}. Indeed G^{+}K = G_{0}, since we have det(K) = O_{F}^{×}/(O_{F}^{×})^{r} and an exact sequence

1 → O_{F}^{×}/(O_{F}^{×})^{r} → F^{×}/(F^{×})^{r} → ℤ/rℤ → 0.

Proposition 5.1. Let I ⊆ ℤ/rℤ be a non-empty set. For i ∈ I, fix α_{i} > 0 and a subset Z_{i} ⊆ X_{{i}} of cardinality ⩾ α_{i} |X_{{i}}|. Then the proportion of elements of (x_{i})_{i∈I} ∈ X_{I} satisfying x_{i} ∈ Z_{i} for every i ∈ I is at least

∏_{i∈I} α_{i} − \frac{2(|I| − 1)}{\sqrt{q}}.

Proof. Proposition 5.1 is obvious for |I| = 1, and it follows by induction on |I| due to the following lemma. □

Lemma 5.2. Fix I ⊆ ℤ/rℤ of cardinality ⩾ 2, and i ∈ I. Write I′ = I \ {i}. For α, α′ > 0, Z ⊆ X_{{i}} of cardinality ⩾ α |X_{{i}}| and Z′ ⊆ X_{I′} of cardinality ⩾ α′ |X_{I′}|, the proportion of (x_{j})_{j∈I} ∈ X_{I} satisfying x_{i} ∈ Z and (x_{j})_{j∈I′} ∈ Z′ is at least

αα′ − \frac{2}{\sqrt{q}} .

Proof. Let T : ℓ^{2}(X_{{i}}) → ℓ^{2}(X_{I′}) be the following averaging operator: for any f ∈ ℓ^{2} (X_{{i}}) and (x_{j})_{j∈I′} ∈ X_{I′}, T (f)((x_{j})_{j∈I′}) is the average of f(x_{i}) over x_{i} ∈ X_{{i}} such that (x_{j})_{j∈I} belongs to X_{I}. We normalize the norms of ℓ^{2}(X_{{i}}) and ℓ^{2}(X_{I′}) such that the constant function 1 has norm 1. We denote by T_{0} : ℓ_{0}^{2}(X_{{i}}) → ℓ_{0}^{2}(X_{I′}) the restriction of T to the hyperplane orthogonal to the constant function 1.

Note that T^{∗}T : ℓ^{2}(X_{{i}}) → ℓ^{2}(X_{{i}}) is also an averaging operator, and in fact it is an average of the Hecke operators H_{λ_{1},...,λ_{r}} for (λ_{1}, ..., λ_{r}) ∈ Λ_{0} such that λ_{r} ⩽ λ_{1} + 2. In this average, the coefficient of H_{0,...,0} = Id is ⩽ q^{−1}. Indeed, let ĩ ∈ ℤ be a lifting of i and let ĩ_{−}, ĩ_{+} be the biggest integer < ĩ (resp. the smallest integer > ĩ) whose images i_{−}, i_{+} belong to I′. Then for any (x_{j})_{j∈I′} ∈ X_{I′}, the number of x_{i} ∈ X_{{i}} such that (x_{j})_{j∈I} belongs to X_{I} is exactly |Gr (ĩ− ĩ_{−}, ĩ_{+} − ĩ_{−}) (𝔽_{q})|, the number of sub-𝔽_{q}-vector spaces of dimension

ĩ− ĩ_{−} in 𝔽_{q}^{ĩ_{+}−ĩ_{−}}. The coefficient of H_{0,...,0} is |Gr (ĩ− ĩ_{−}, ĩ_{+} − ĩ_{−}) (𝔽_{q})|^{−1}, and it is clear that

|Gr (ĩ− ĩ_{−}, ĩ_{+} − ĩ_{−}) (𝔽_{q})| ⩾ q. By (10) we have

∥T_{0}^{∗}T_{0}∥_{L(ℓ_{0}^{2}(X_{\{i\}}))} ⩽ \frac{1}{q} + \frac{3}{q} = \frac{4}{q},

implying that ∥T_{0}∥_{L(ℓ_{0}^{2}(X_{\{i\}}),ℓ_{0}^{2}(X_{I′}))} ⩽ 2q^{− \frac{1}{2}} . Therefore

|⟨T (1_{Z}), 1_{Z′}⟩ − \frac{|Z| · |Z′|}{|X_{\{i\}}| · |X_{I′}|}| ⩽ 2q^{− \frac{1}{2}} \sqrt{\frac{|Z| · |Z′|}{|X_{\{i\}}| · |X_{I′}|}} ⩽ 2q^{− \frac{1}{2}} ,  (11)

completing the proof of Lemma 5.2. □

Remark 5.1. If X = Γ\G/K is assumed to be a Ramanujan complex (see [22]) we can improve the estimate in (10), but at the end, in (11), we get the same exponent −\frac{1}{2}.

Proposition 5.1 has the following corollary.

Corollary 5.3. Let I ⊆ ℤ/rℤ be of cardinality ⩾ 2. Let X_{I} be the |I|-uniform hypergraph with vertices X = Γ\G/K and with hyperedges the set X_{I} of faces of X of type I. Then for q large enough (as a function of |I| alone) the overlap parameter of X_{I} is bounded below by a positive constant depending only on |I|.

Proof. Let f : X → ℝ^{|I|−1} be an injection. By the main result of [27] (which is a strengthening of Theorem 1.2), applied to the sets f (X_{{i}}) ⊆ ℝ^{|I|−1} for i ∈ I, we obtain sets P_{i} ⊆ f (X_{{i}}) with |P_{i}| ⩾ c′′_{|I|−1} |X_{{i}}|, for i ∈ I, such that all the simplices with vertices in each of the P_{i} have a point in common. Here c′′_{|I|−1} is a constant depending only on |I|. By an application of Proposition 5.1 to the sets Z_{i} = f^{−1}(P_{i}) with α_{i} = c′′_{|I|−1}, we see that if

q > \frac{16(|I| − 1)^{2}}{(c′′_{|I|−1})^{2|I|}}

then the overlap parameter of Γ\G/K is at least \frac{1}{2} (c′′_{|I|−1})^{|I|}. □

Lemma 5.4. For any integer r and for any non-archimedian local field F, there exists a cocompact lattice Γ in G_{0} which satisfies condition (C), and a sequence of finite index subgroups Γ_{n} ⊆ Γ with lim_{n→∞} |Γ/Γ_{n}| = ∞.

Proof. We start by choosing any cocompact arithmetic subgroup Γ̃ in G = P GL_{r}(F). The existence of a cocompact arithmetic subgroup is well-known: use division algebras over function fields when the characteristic of F is finite and unitary groups over number fields when the characteristic of F is 0. In the case of characteristic 0, it is a particular case of a theorem of Borel and Harder [7]; see also Example 5.1.4, Corollary 5.12 and the remark after it in [6], for a short proof. Since G/G_{0} = ℤ/rℤ, \overline{Γ} = Γ̃ ∩ G_{0} is of finite index in Γ̃. Since \overline{Γ} is a cocompact lattice in G_{0}, the elements γ ∈ \overline{Γ} \ \{1\}, such that there exists x ∈ G/K with d(x, γx) ⩽ 2, form a finite number of conjugacy classes. By its arithmetic nature, \overline{Γ} embeds in the product of its finite quotients. Therefore there is a finite index subgroup Γ ⊆ \overline{Γ} which satisfies condition (C) and a sequence of finite index subgroups Γ_{n} of Γ with lim_{n→∞} |Γ/Γ_{n}| = ∞. □

Corollary 5.3, applied (for r ⩾ 3) to the lattices Γ_{n} of Lemma 5.4, yields highly overlapping families of |I|-uniform hypergraphs. In the particular case where I = ℤ/rℤ, these hypergraphs are finite quotients of the building of P GL_{r}(F) and their hyperedges are the images of the chambers of the building.

Proof of Theorem 1.5. Theorem 1.5 is a consequence of Corollary 5.3, applied to the Ramanujan complexes constructed in [21] (which are based on a lattice construction from [12]), together with their description in [21] as the clique complexes corresponding to the Cayley graphs associated to certain (explicitly defined) generators of P GL_{r}(F), where F = 𝔽_{p}((t)). We just need to ensure that the corresponding lattices are sublattices of G_{0} (so that they preserve the type), as well as that condition (C) is satisfied. This is true for arbitrarily large m due to Corollary 6.8 of [21], or equivalently the case r = d of Theorem 7.1 in [21]. Alternatively, one can consider the construction of the Ramanujan complexes in [31], specifically the second extreme distinguished case of Corollary 36 in [31]. □

6. A Szemerédi-type theorem for infinite hypergraphs

In a measurable space, an atom is a measurable set which has positive measure and contains no set of smaller but positive measure. A measure which has no atoms is called non-atomic. A basic result of Sierpinski [32] states that if μ is a non-atomic measure, then for any measurable set A and any b with 0 ⩽ b ⩽ μ(A), there is a measurable subset B of A with μ(B) = b. Given a measurable space on a set V and a measure μ, the h-fold product measurable space is generated by all sets B_{1} × ⋯ × B_{h}, with B_{1}, …, B_{h} measurable subsets of V, and the product measure μ^{h} is the unique measure on this space given by μ^{h}(B_{1} × ⋯ × B_{h}) = μ(B_{1}) ⋯ μ(B_{h}).

The aim of this section is to establish a Szemerédi-type theorem for infinite hypergraphs with a non-atomic measure on their vertex sets. The statement will be used in the next section, for the proof of Theorem 1.8.

Given a finite or infinite h-uniform hypergraph G = (V, E), we say that an h-tuple (V_{1}, …, V_{h}) of disjoint subsets of V is homogeneous with respect to G if either all elements of V_{1} × … × V_{h} are hyperedges of G or none of them are. If, in addition, we have a finite non-atomic measure μ on V, we say that G is (c, μ)-structured provided that for all disjoint measurable subsets S_{1}, …, S_{h} ⊆ V, there exist measurable Y_{i} ⊆ S_{i} for 1 ⩽ i ⩽ h with μ(Y_{i}) ⩾ cμ(S_{i}) such that the h-tuple (Y_{1}, …, Y_{h}) is homogeneous. The following theorem generalizes a result in [28], where the case h = 2 was settled. The proof is based on an idea of Komlós.

Theorem 6.1. For any c, ε > 0 and for any positive integer h, there is K = K(h, c, ε) such that the following statement is true. If G = (V, E) is a (c, μ)-structured h-uniform hypergraph, where μ is a non-atomic measure μ, then for each k ⩾ K there is a partition V = V_{1} ∪ … ∪ V_{k} of V into k parts of equal measure such that all but at most an ε-fraction of the h-tuples (V_{i_{1}}, …, V_{i_{h}}) are homogeneous.

In the sequel, let G = (V, E) be a fixed h-uniform hypergraph with a finite non-atomic measure μ on V. The measure of G, denoted by μ(G), is the product measure μ^{h} of the set of h-tuples (v_{1}, …, v_{h}) ∈ V^{h} with {v_{1}, …, v_{h}} an edge of G (we assume throughout that this set is μ^{h}-measurable). Define the edge-density d(G) of G to be \frac{μ(G)}{μ(V)^{h}}. For measurable vertex subsets V_{1}, …, V_{h}, define

ν(V_{1}, …, V_{h}) =^{def} μ^{h}((v_{1}, …, v_{h}) ∈ V_{1} × ⋯ × V_{h} : {v_{1}, …, v_{h}} ∈ E),  (12)

and the edge density

d(V_{1}, …, V_{h}) =^{def} \frac{ν(V_{1}, …, V_{h})}{μ(V_{1}) ⋯ μ(V_{h})}.

An h-tuple of disjoint subsets (X_{1}, …, X_{h}) of vertices in an h-uniform hypergraph is said to be (γ, δ)-superregular if for any subsets Y_{i} ⊆ X_{i} with μ(Y_{1}) ⋯ μ(Y_{h}) ⩾ γμ(X_{1}) ⋯ μ(X_{h}), we have d(Y_{1}, …, Y_{h}) ⩾ δ.

The following lemma shows that the vertex set of any dense h-uniform hypergraph can be partitioned into h parts of equal measure such that the sub-hypergraph formed by all of its edges that contain one point from each part is still relatively dense. The analogue of this statement for finite hypergraphs is well known and very easy to prove, as a uniformly random partition of the vertex set into equal parts will almost surely work. Here we do not have the leisure of taking such a uniform random partition.

Lemma 6.2. Let G = (V, E) be an h-uniform hypergraph, μ a finite non-atomic measure on V. Then there is a partition V = V_{1} ∪ … ∪ V_{h} into measurable subsets, each of measure μ(V)/h, such that d(V_{1}, …, V_{h}) ⩾ \frac{d(G)}{2}.

Proof. Write t = h⌈h/d(G)⌉. Arbitrarily partition V into t subsets V = U_{1} ∪ … ∪ U_{t}, each of measure μ(V)/t. This can be done since μ is non-atomic. The product measure of the set of h-tuples of vertices from distinct U_{i} is at least

∏_{i=0}^{h−1} (1 − \frac{i}{t}) μ(V) ⩾ (1 − \frac{\binom{h}{2}}{t}) μ(V)^{h} ⩾ (1 − \frac{h^{2}}{2t} ) μ(V)^{h} ⩾ (1 − \frac{d(G)}{2}) μ(V)^{h}.

Hence, the edge density of the sub-hypergraph of G with vertices in different U_{i} is at least d(G) − d(G)/2 = d(G)/2. We randomly partition V = V_{1} ∪ … ∪ V_{h}, where each V_{i} is a union of t/h of the U_{j}, with each such partition being equally likely. For U_{j_{1}}, …, U_{j_{h}} with j_{1} < … < j_{h}, the probability that U_{j_{i}} ⊆ V_{i} for all 1 ⩽ i ⩽ h is at least h^{−h}. Hence, by linearity of expectation and the fact μ(V_{1}) ⋯ μ(V_{h}) = h^{−h}μ(V)^{h}, the expected value of d(V_{1}, …, V_{h}) is at least d(G)/2. It follows that there is a partition V = V_{1} ∪ … ∪ V_{h} into parts of equal measure with d(V_{1}, …, V_{h}) ⩾ d(G)/2. □

The next lemma shows that if an h-tuple of sets is not (γ, δ)-superregular, then we can find subsets of large measure such that the edge density between them is significantly larger than the edge density between the original h-tuple.

Lemma 6.3. Let G = (V, E) be an h-uniform hypergraph and μ a finite non-atomic measure on V. If a collection of h measurable vertex subsets (W_{1}, …, W_{h}) with d(W_{1}, …, W_{h}) = c is not (δ, γ)-superregular, then there are subsets Z_{i} ⊆ W_{i} for 1 ⩽ i ⩽ h such that

μ(Z_{1}) … μ(Z_{h}) ⩾ \frac{δγ}{2^{h}} μ(W_{1}) ⋯ μ(W_{h})

and

d(Z_{1}, …, Z_{h}) ⩾ c + (c − 2δ)\frac{γ}{1 − γ} .

Proof. Since (W_{1}, …, W_{h}) is not (δ, γ)-superregular, there exist subsets Y_{i} ⊆ W_{i} for every 1 ⩽ i ⩽ h with

μ(Y_{1}) ⋯ μ(Y_{h}) ⩾ γμ(W_{1}) ⋯ μ(W_{h}) and d(Y_{1}, …, Y_{h}) < δ.  (13)

The sum of all the 2^{h} terms ν(T_{1}, …, T_{h}) (where ν is defined in (12)) with T_{i} = Y_{i} or T_{i} = W_{i} \ Y_{i} equals ν(W_{1}, …, W_{h}) = cμ(W_{1}) ⋯ μ(W_{h}). The sum of ν(T_{1}, …, T_{h}) over all such terms with not all T_{i} = Y_{i} and with

μ(T_{1}) ⋯ μ(T_{h}) ⩾ \frac{δγ}{2^{h}} μ(W_{1}) ⋯ μ(W_{h})

is therefore greater than

(c − 2^{h} \frac{δγ}{2^{h}} ) μ(W_{1}) ⋯ μ(W_{h}) − δμ(Y_{1}) ⋯ μ(Y_{h}) ⩾ cμ(W_{1}) ⋯ μ(W_{h}) − 2δμ(Y_{1}) ⋯ μ(Y_{h}).

Here we used both inequalities in (13). Also, the sum of μ(T_{1}) ⋯ μ(T_{h}) over these terms is at most μ(W_{1}) ⋯ μ(W_{h})−μ(Y_{1}) ⋯ μ(Y_{h}). By averaging, if a_{1}+⋯+a_{k} ⩾ A and b_{1}+⋯+b_{k} ⩽ B with all a_{i}, b_{i} positive, then there is 1 ⩽ i ⩽ k such that \frac{a_{i}}{b_{i}} ⩾ \frac{A}{B}. Hence, there are T_{1}, …, T_{h} with T_{i} = Y_{i} or T_{i} = W_{i}\Y_{i} and not all T_{i} = Y_{i}, with μ(T_{1}) ⋯ μ(T_{h}) ⩾ 2^{−h}δγμ(W_{1}) ⋯ μ(W_{h}) and

d(T_{1}, …, T_{h}) = \frac{ν(T_{1}, …, T_{h})}{μ(T_{1}) ⋯ μ(T_{h})} ⩾ \frac{cμ(W_{1}) ⋯ μ(W_{h}) − 2δμ(Y_{1}) ⋯ μ(Y_{h})}{μ(W_{1}) ⋯ μ(W_{h}) − μ(Y_{1}) ⋯ μ(Y_{h})}

= c + (c − 2δ)\frac{μ(Y_{1}) ⋯ μ(Y_{h})}{μ(W_{1}) ⋯ μ(W_{h}) − μ(Y_{1}) ⋯ μ(Y_{h})} ⩾ c + (c − 2δ)\frac{γ}{1 − γ} ,

as required. □

By repeated application of Lemma 6.3, we obtain the following result, which shows that a dense hypergraph contains a superregular h-tuple of sets of large measure.

Lemma 6.4. For γ, δ > 0 and a positive integer h, there is α = α(γ, δ, h) such that the following holds. If G = (V, E) is an h-uniform hypergraph, μ is a finite non-atomic measure on V with d(G) ⩾ 8δ, then there is an h-tuple (X_{1}, …, X_{h}) of disjoint measurable vertex subsets, which is (γ, δ)-superregular and satisfies μ(X_{1}) ⋯ μ(X_{h}) ⩾ αμ(V)^{h}.

Proof. Define

α = \frac{1}{h^{h}} (\frac{δγ}{2^{h}} )^{\frac{2}{γ} log_{2}(1/δ)} .

By Lemma 6.2, there is a partition V = V_{1} ∪ … ∪ V_{h} into parts of equal measure such that d =^{def} d(V_{1}, …, V_{h}) ⩾ d(G)/2. We will repeatedly apply Lemma 6.3, starting with the sets V_{1}, …, V_{h}, until we get a (γ, δ)-superregular h-tuple.

If (V_{1}, …, V_{h}) is not (γ, δ)-superregular, then we can find V_{1}^{1} ⊆ V_{1}, …, V_{h}^{1} ⊆ V_{h} with

μ(V_{1}^{1}) ⋯ μ(V_{h}^{1}) ⩾ \frac{δγ}{2^{h}} μ(V_{1}) ⋯ μ(V_{h})

and

d (V_{1}^{1}, …, V_{h}^{1}) ⩾ d + (d − 2δ)\frac{γ}{1 − γ} > d (1 + \frac{γ}{2} ) .

After k iterations, we either have found a (γ, δ)-superregular h-tuple, or we find V_{1}^{k}, …, V_{h}^{k} with

μ(V_{1}^{k}) ⋯ μ(V_{h}^{k}) ⩾ (\frac{δγ}{2^{h}} )^{k} μ(V_{1}) ⋯ μ(V_{h})

and

d (V_{1}^{k}, …, V_{h}^{k}) > d (1 + \frac{γ}{2} )^{k} .

This cannot continue for more than k_{0} = \frac{2}{γ} log_{2}(1/d) iterations, as otherwise we would produce an h-tuple of density more than 1, a contradiction. Thus, at some step k ⩽ k_{0}, we find an h-tuple of sets X_{i} =^{def} V_{i}^{k} with

μ(X_{1}) ⋯ μ(X_{h}) ⩾ (\frac{δγ}{2^{h}} )^{k} μ(V_{1}) ⋯ μ(V_{h}) = \frac{1}{h^{h}} (\frac{δγ}{2^{h}} )^{k} μ(V)^{h} ⩾ αμ(V)^{h},

which is (γ, δ)-superregular. □

An h-uniform hypergraph H = (V, E) is h-partite if there is a partition V = V_{1} ∪ … ∪ V_{h} such that every edge has exactly one vertex in each V_{i}. For a vertex set V, and a collection C of h-tuples A_{1}, …, A_{h} of vertex subsets of V, define the hypergraph H(C) on V, which is the union of the complete h-partite h-uniform hypergraphs with parts A_{1}, …, A_{h}.

Lemma 6.5. For c, ε > 0 and a positive integer h, there is L = L(h, c, ε) such that the following statement is true. If G = (V, E) is a (c, μ)-structured h-uniform hypergraph with μ a finite non-atomic measure, then there is a collection C of at most L homogeneous h-tuples of vertex subsets such that the density of H(C) is at least 1 − ε.

Proof. Let H_{0} denote the complete h-uniform hypergraph on V, and let γ = c^{h}, δ = ε/8, α = α(γ, δ, h) as in Lemma 6.4, β = h!δc^{h}α, and L = β^{−1}. Suppose that for some i ⩾ 1, we have already defined H_{i−1}. If G has an h-tuple A_{1}, …, A_{h} of disjoint subsets which is homogeneous and such that the hypergraph which consists of those edges of H_{i−1} that have one vertex in each A_{ℓ} has edge density at least β, then let H_{i} denote the sub-hypergraph of H_{i−1} obtained by deleting all edges with one vertex in each A_{ℓ}. Otherwise, we stop. This process will clearly terminate in j ⩽ β^{−1} steps with an h-uniform hypergraph H_{j} as d(H_{i}) ⩽ 1 − iβ for each i.

We next show that d(H_{j}) < ε. Indeed, otherwise by Lemma 6.4, H_{j} has a collection of h disjoint vertex subsets (X_{1}, …, X_{h}) which is (γ, δ)-superregular with

μ(X_{1}) ⋯ μ(X_{h}) ⩾ αμ(V)^{h}.

Since G is (c, μ)-structured, there are subsets A_{i} ⊆ X_{i} for 1 ⩽ i ⩽ h with μ(A_{i}) ⩾ cμ(X_{i}) such that (A_{1}, …, A_{h}) is homogeneous with respect to G. As γ = c^{h},

μ(A_{1}) ⋯ μ(A_{h}) ⩾ γμ(X_{1}) ⋯ μ(X_{h}),

and (X_{1}, …, X_{h}) is (γ, δ)-superregular, we have d(A_{1}, …, A_{h}) ⩾ δ, and hence the hypergraph which consists of those edges of H_{j} that have one vertex in each A_{ℓ} has edge density at least

h!δ · \frac{μ(A_{1}) ⋯ μ(A_{h})}{μ(V)^{h}} ⩾ h!δc^{h} · \frac{μ(X_{1}) ⋯ μ(X_{h})}{μ(V)^{h}} ⩾ h!δc^{h}α = β.

However, this contradicts the fact that since the construction terminated at the jth step, there are no such subsets A_{1}, …, A_{h}. □

For an h-uniform hypergraph G = (V, E) and a vertex partition P = {V = V_{1} ∪ … ∪ V_{k}}, the homogeneous hypergraph G_{P} is the h-uniform hypergraph on V where (v_{1}, …, v_{h}) ∈ V_{i_{1}} × ⋯ × V_{i_{h}} is an edge if and only if (V_{i_{1}}, …, V_{i_{h}}) is homogeneous with respect to G. Note that if P′ is a refinement of P, then d(G_{P′}) ⩾ d(G_{P}). Given a collection C of h-tuples (A_{1}, …, A_{h}) which are homogeneous in G, define the partition P of V into (h + 1)^{|C|} parts, where each part consists of those vertices in the same A_{i} (or in none of the A_{i}) for each htuple in C. The hypergraph G_{P} contains the hypergraph H(C). Hence, we have the following corollary of Lemma 6.5 with M = (h + 1)^{L}.

Corollary 6.6. For any c, ε > 0 and for any positive integer h, there is M = M(h, c, ε) such that the following statement is true. If G = (V, E) is a (c, μ)-structured h-uniform hypergraph with a finite non-atomic measure μ on its vertex set, then there is a partition P of V into at most M parts such that d(G_{P}) ⩾ 1 − ε.

Proof of Theorem 6.1. Let M = M(h, c, \frac{ε}{2}) as in Corollary 6.6 and K be the smallest integer which is at least 2Mhε^{−1}. Fix k ⩾ K. By Corollary 6.6, there is a partition P′ of V into at most M parts such that d(G_{P′}) ⩾ 1 − \frac{ε}{2}. If V_{i} is a part of P′, arbitrarily partition V_{i} into parts of measure μ(V)/k and one remaining piece of measure at most μ(V)/k. Let W be the union of the remaining parts, so μ(W) ⩽ Mμ(V)/k, and arbitrarily partition W into parts of measure μ(V)/k. We have thus produced a partition P into k parts of equal measure, and we next show that this partition satisfies the assertion of Theorem 6.1. The edge density of the hypergraph of h-tuples in V^{h} that contain a vertex in W is at most

1 − (1 − \frac{μ(W)}{μ(V)})^{h} ⩽ h\frac{μ(W)}{μ(V)} ⩽ \frac{hM}{k} ⩽ \frac{ε}{2}.

Thus d(G_{P}) ⩾ d(G_{P′}) − \frac{ε}{2} ⩾ 1 − ε, and hence the partition P satisfies the conclusion of Theorem 6.1. □

7. A partition result—Proof of Theorem 1.8

Before proving Theorem 1.8 in its full generality, we give a simple argument for the special case d = 2, which provides a good upper bound on the constant K(ε, 2).

Proposition 7.1. Let ε > 0 and k ⩾ \frac{12}{ε} + 1. For any finite Borel measure μ on ℝ^{2} with respect to which every line has measure 0, and for any point q ∈ ℝ^{d}, there is a partition ℝ^{2} = A_{1} ∪ … ∪ A_{k} into k measurable parts of equal measure, such that all but at most an ε-fraction of the triples A_{h}, A_{i}, A_{j} are homogenous with respect to q.

Proof. Partition ℝ^{2} radially around q into k cones A_{1}, …, A_{k} of equal measure. Notice that a triple A_{h}, A_{i}, A_{j} is not homogeneous with respect to q if and only if one of them intersects the reflection of another about q. Since the number of such triples of cones is at most 2k(k − 2), the fraction of nonhomogeneous triples cannot exceed 2k(k − 2)/\binom{k}{3} = 12/(k − 1) ⩽ ε, which completes the proof. □

Next we turn to the proof of Theorem 1.8 in the general case. We break the proof into four lemmas. For the first one, we recall Radon’s theorem, which states that any set of d + 2 points in ℝ^{d} can be partitioned into two sets whose convex hulls have nonempty intersection (see [16]).

Lemma 7.2. Let v_{1}, …, v_{d+1} ∈ ℝ^{d}. A point q ∈ ℝ^{d} belongs to the simplex with vertex set V = {v_{1}, …, v_{d+1}} ⊆ ℝ^{d} if and only if for each nonempty proper subset X ⊆ V, there is a hyperplane passing through q which separates X from V \ X.

Proof. In one direction the statement is clear, as there is a hyperplane through any internal point separating any proper subset of the vertex set from its complement. In the other direction, suppose q is not in the simplex, and consider the set V ∪ {q} of d + 2 points. By Radon’s theorem, there is a partition V ∪ {q} = A ∪ B such that the convex hull of A and the convex hull of B have a point p in common. Suppose without loss of generality that q ∈ A. Clearly, |A| > 1, because q is outside of the simplex. But then A \ {q} and B cannot be separated by a hyperplane passing through q. □

We need the following version of the ham sandwich theorem (see, e.g., [24]).

Lemma 7.3. Let S_{1}, …, S_{d−1} be measurable subsets of ℝ^{d} and q ∈ ℝ^{d}. There is a hyperplane through q that partitions each S_{i} into two parts of equal measure.

By repeated application of Lemma 7.3, and then using Lemma 7.2, we obtain:

Lemma 7.4. For any positive integer d, there is c_{d} > 0 satisfying the following condition. Let μ be a finite Borel measure on ℝ^{d} with respect to which every hyperplane has measure 0, let S_{1}, …, S_{d+1} be measurable subsets of ℝ^{d}, and let q ∈ ℝ^{d}. Then there exist Y_{i} ⊆ S_{i} for all 1 ⩽ i ⩽ d + 1 such that μ(Y_{i}) ⩾ c_{d}μ(S_{i}) and Y_{1}, …, Y_{d+1} are homogeneous with respect to q.

Proof. Consider an arbitrary labeling X_{1}, …, X_{2^{d+1}−2} of the nonempty proper subsets of [d + 1] = {1, …, d + 1}. We describe an iterative process for constructing the desired sets Y_{1}, …, Y_{d+1}.

Let S_{j}^{0} = S_{j}, for every j ∈ [d + 1]. After completing step i, we will have subsets S_{j}^{i} ⊆ S_{j} with μ(S_{j}^{i}) ⩾ 2^{−i}μ(S_{j}) such that at least one of the following two conditions is satisfied:

(1) there is a hyperplane through q such that S_{1}^{i} ∪ S_{2}^{i} ∪ … ∪ S_{d+1}^{i} lies entirely on one of its sides, or

(2) for every 1 ⩽ k ⩽ i, there is a hyperplane through q that separates the sets {S_{j}^{i}}_{j∈X_{k}} from the sets {S_{j}^{i}}_{j∈[d+1]\X_{k}}.

The proof shows that we can take c_{d} = 2^{2−2^{d+1}}. Notice that the inductive hypothesis holds vacuously at the end of step 0. Suppose we have already completed step i and we wish to proceed to the next step.

If condition (1) is satisfied, then we simply let S_{j}^{i+1} = S_{j}^{i}. Thus, we may suppose that condition (2) is satisfied. Let a ∈ X_{i+1} and b ∈ [d + 1] \ X_{i+1}. We apply Lemma 7.3 to the d − 1 sets S_{j}^{i} with j ∈ [d + 1] \ {a, b}. There is a hyperplane H containing q that separates each such S_{j}^{i} into parts of equal measure. The hyperplane H partitions S_{a}^{i} into two subsets. Let S_{a}^{i+1} be the subset of larger measure. Similarly, H partitions S_{b}^{i} into two subsets. Let S_{b}^{i+1} be the subset of larger measure. If S_{a}^{i+1} and S_{b}^{i+1} are on the same side of H, then let S_{j}^{i+1} for j ∈ [d+1]\{a, b} be the subset of S_{j}^{i} consisting of those points on the same side of H as S_{a}^{i+1} and S_{b}^{i+1}. In this case, we have μ(S_{j}^{i+1}) ⩾ \frac{1}{2}μ(S_{j}^{i}) ⩾ 2^{−i−1}μ(S_{j}), the first of the two desired properties holds, and we have completed step i + 1. Otherwise, for j ∈ X_{i+1} \ {a}, let S_{j}^{i+1} be the subset of S_{j}^{i} consisting of those points on the same side of H as S_{a}^{i+1}, and for j ∈ [d + 1] \ (X_{i+1} ∪ {b}), let S_{j}^{i+1} be the subset of S_{j}^{i} consisting of those points on the same side of H as S_{b}^{i+1}. By construction, we have μ(S_{j}^{i+1}) ⩾ \frac{1}{2}μ(S_{j}^{i}) ⩾ 2^{−i−1}μ(S_{j}), the second of the two desired properties holds, and we have completed step i + 1.

We may therefore assume that we finish the iterative process, and in the end we have sets Y_{j} = S_{j}^{2^{d+1}−2} with μ(Y_{j}) ⩾ 2^{2−2^{d+1}}μ(S_{j}) for 1 ⩽ j ⩽ d + 1, and for each 1 ⩽ k ⩽ 2^{d+1} − 2, there is a hyperplane through q that separates the sets {Y_{j}}_{j∈X_{k}} from the sets {Y_{j}}_{j∈[d+1]\X_{k}}. By Lemma 7.2, this implies that every simplex with one vertex in each Y_{j} contains q. □

We are now ready to complete the proof of Theorem 1.8. Given a point q ∈ ℝ^{d}, define the hypergraph H_{q} with vertex set ℝ^{d} as the set of all (d+1)-tuples of points whose convex hulls contain q. Lemma 7.4 states that for each finite measure μ on ℝ^{d} such that every hyperplane has measure 0, the hypergraph H_{q} is (c_{d}, μ)-structured. Theorem 1.8 then follows from Theorem 6.1.

8. Optimal sparse constructions in space—Proof of Theorem 1.7

In this section, we deduce Theorem 1.7 from Corollary 1.9. Let H = (V, E) be a (d + 1)- uniform hypergraph. The edge density

ρ(H) =^{def} \frac{|E|}{\binom{|V |}{d+1}}

is the fraction of (d+1)-tuples that are hyperedges of H. For vertex subsets V_{1}, …, V_{d+1} ⊆ V, the edge density ρ(V_{1}, …, V_{d+1}) is defined as the fraction of (d + 1)-tuples in V_{1} × … × V_{d+1} that are hyperedges of H.

Proof of Theorem 1.7. Let t = 8d^{2}/ε, so that for any equipartition of the vertex set of a complete (d + 1)-uniform hypergraph into k ⩾ t parts, all but at most an \frac{ε}{8}-fraction of its hyperedges have their vertices in different parts. Indeed, the fraction of hyperedges with one vertex in each part is

(\frac{n}{k})^{d+1} · \begin{matrix}( & {k \atop d+1} & ) \\ ( & {n \atop d+1} & ) \end{matrix} ⩾ ∏_{i=1}^{d} (1 − \frac{i}{k} ) ⩾ 1 − \frac{d^{2}}{k} ⩾ 1 − \frac{ε}{8}.

Let K = K(ε/8, d) be the constant from Corollary 1.9, and k = max{K, t}.

Let r(d, ε) be sufficiently large so that for any r ⩾ r(d, ε) and n a sufficiently large multiple of d + 1, there is an r-regular (d + 1)-uniform hypergraph H on n vertices, whose hyperedges are uniformly distributed in the sense that for any disjoint vertex subsets V_{1}, …, V_{d+1} ⊆ V (H) with |V_{i}| ⩾ \frac{n}{k} for 1 ⩽ i ⩽ d + 1,

|\frac{ρ(V_{1}, …, V_{d+1})}{ρ(H)} − 1| ⩽ \frac{ε}{4}.  (14)

The existence of an integer r(d, ε) and a hypergraph H with the above properties follows from the standard fact that an n-vertex r-regular (d + 1)-uniform hypergraph H chosen uniformly at random from all n-vertex r-regular (d + 1)-uniform hypergraphs, meets the requirements for large enough r with probability tending to 1 as n → ∞.

Let P ⊆ ℝ^{d} satisfy |P | = n. Since n is sufficiently large, there is a point q that is in at least c(d) − \frac{ε}{4} fraction of the simplices with vertices in P. Since k ⩾ K, by Corollary 1.9, there is an equipartition P = P_{1} ∪ … ∪ P_{k} such that all but at most an \frac{ε}{8}-fraction of the (d + 1)-tuples P_{i_{1}}, …, P_{i_{d+1}} are homogenous with respect to q. Since k ⩾ t, all but at most an \frac{ε}{8} + \frac{ε}{8} = \frac{ε}{4}-fraction of the (d + 1)-tuples of points of P have their vertices in d + 1 different parts of the partition, and these parts are homogeneous. Since q is in at least a fraction c(d) − \frac{ε}{4} of the simplices with vertices in P, at least a fraction c(d) − \frac{ε}{2} of the (d + 1)-tuples of points of P span a simplex containing q and having its vertices in d + 1 different parts of the partition such that these parts are homogeneous.

Let f : V (H) → P be an arbitrary bijection between the vertices of H and P. Write V_{i} = f^{−1}(P_{i}) for 1 ⩽ i ⩽ k. Note that if P_{i_{1}}, P_{i_{2}}, …, P_{i_{d+1}} are homogeneous with respect to q such that there is a simplex containing q with one vertex in each of these parts, then necessarily all the simplices with one vertex in each of these parts contains q. By (14), for all d + 1 parts V_{i_{1}}, …, V_{i_{d+1}}, the hyperedge density in H between these parts is at least (1 − \frac{ε}{4}) ρ(H). Putting this together with the previous paragraph, we get that at least a fraction (c(d) − \frac{ε}{2}) (1 − \frac{ε}{4}) ⩾ c(d) − ε of the hyperedges of H induce simplices containing q. We conclude that c(H) ⩾ c(d) − ε. □

9. Sparse hypergraphs with nearly maximal overlap number

Here we prove the following result, which implies Theorem 1.6.

Theorem 9.1. Let d and Δ be positive integers and ε > 0. If n ⩾ 2^{9}ε^{−3}d^{9}Δ^{3} and H is a (d+1)-uniform hypergraph with n vertices, maximum degree Δ, and without isolated vertices, and P is a set of n points in ℝ^{d} such that no point in ℝ^{d} is in a fraction more than c of the simplices with vertices in P, then there is a bijection f : V (H) → P such that no point of ℝ^{d} is in a fraction more than c + ε of the simplices whose vertices are the image by f of a hyperedge of H.

We actually show that almost surely we may take f to be a uniform random bijection.

We shall use below Azuma’s inequality (see, e.g., [1]), which asserts that if c = X_{0}, …, X_{n} is a martingale with |X_{a+1} − X_{a}| ⩽ t for all 0 ⩽ a ⩽ n − 1, then

Pr [|X_{n} − c| > λ\sqrt{n}] < 2e^{− \frac{λ^{2}}{2t^{2}}} .  (15)

Let H and F be hypergraphs each with the same number of vertices. For a bijection f : V (H) → V (F), let m_{f} denote the number of hyperedges of H whose image is a hyperedge of F.

Lemma 9.2. Let H and F be k-uniform hypergraphs each with n vertices such that H has maximum degree Δ. Then the probability that for a random bijection f : V (H) → V (F), the

number m_{f} deviates from |E(H)| · |E(F)|/\binom{n}{k} by more than λ\sqrt{n} is at most 2e^{− \frac{λ^{2}}{2(2k+1)^{2}Δ^{2}}} .

Proof. Let e_{1}, …, e_{|E(H)|} denote the hyperedges of H. For a hyperedge e_{j}, let X(e_{j}) be the indicator random variable of the event that the image of e_{j} by f is a hyperedge of F. That is, X(e_{j}) = 1 if f(e_{j}) is a hyperedge of F, and X(e_{j}) = 0 otherwise. Let Y denote the random variable counting the number of hyperedges of H whose image is a hyperedge of F, so Y = ∑_{j=1}^{|E(H)|} X(e_{j}). Each hyperedge of H has a probability |E(F)|/\binom{n}{k} of being mapped by f to a hyperedge of F. By linearity of expectation, the expected value of Y is 𝔼[Y] = |E(H)| · |E(F)|/\binom{n}{k}.

Let V (H) = [n] = {1, …, n}. For a = 0, …, n, let X_{a}(e_{j}) be the probability of the event that the image of e_{j} by f is a hyperedge of F after picking f(1), …, f(a), and let Y_{a} =^{def} ∑_{j=1}^{|E(H)|} X_{a}(e_{j}) denote the expected value of Y after picking f(1), …, f(a). So Y_{0} denotes the expected value of m_{f}, which is |E(H)| · |E(F)|/\binom{n}{k}.

By construction, {Y_{a}}_{a=0}^{n} is a martingale. We next give an upper bound on

|Y_{a+1} − Y_{a}| ⩽ ∑_{j=1}^{|E(H)|} |X_{a+1}(e_{j}) − X_{a}(e_{j})|,

so as to apply Azuma’s inequality (15). For the ⩽ Δ hyperedges e_{j} that contain a + 1, we bound |X_{a+1}(e_{j}) − X_{a}(e_{j})| ⩽ 1. For those hyperedges with all vertices in {1, …, a}, we have X_{a+1}(e_{j}) = X_{a}(e_{j}). Let e_{j} be a hyperedge which does not contain a + 1, and contains a vertex which is more than a + 1. Let i_{1}, …, i_{h} be the vertices of e_{j} that are at most a, so h < k as e_{j} contains a vertex which is more than a+1. Let w(e_{j}) = k −h denote the number of vertices of e_{j} which are greater than a + 1. All of these vertices are in {a + 2, …, n}, and therefore n − a ⩾ k − h + 1. It follows that

n − a − w(e_{j}) = n − a − k + h = \frac{n − a}{k} + (1 − \frac{1}{k}) (n − a) − k + h

⩾ \frac{n − a}{k} + (1 − \frac{1}{k}) (k − h + 1) − k + h = \frac{n − a − 1}{k} + \frac{h}{k} ⩾ \frac{n − a − 1}{k}. (16)

Let Z denote the number of hyperedges of F that contain f(i_{1}), …, f(i_{h}) and whose remaining vertices are in V (F)\{f(1), …, f(a)}, and Z′ denote the number of hyperedges of F that contain f(i_{1}), …, f(i_{h}) and whose remaining vertices are in V (F)\{f(1), …, f(a), f(a+1)}.

We have Z ⩾ Z′ ⩾ Z − \binom{n−a−1}{k−h−1}, as f(i_{1}), …, f(i_{h}), f(a + 1) are in at most \binom{n−a−1}{k−h−1} hyperedges of F whose remaining vertices are in V (F) \ {f(1), …, f(a), f(a + 1)}. We also have

Z ⩽ \binom{n−a}{k−h}. Note that X_{a}(e_{j}) = \frac{Z}{\binom{n−a}{k−h}} and X_{a+1}(e_{j}) = \frac{Z′}{\binom{n−a−1}{k−h}}. Hence,

|X_{a}(e_{j}) − X_{a+1}(e_{j})| = |\frac{Z}{\binom{n−a}{k−h}} − \frac{Z′}{\binom{n−a−1}{k−h}} |

⩽ Z (\binom{n − a − 1}{k − h}^{−1} − \binom{n − a}{k − h}^{−1}) + (Z − Z′)\binom{n − a − 1}{k − h}^{−1}

⩽ (\frac{n − a}{n − a − k + h} − 1) + \frac{k − h}{n − a − k + h}
= \frac{2(k − h)}{n − a − k + h}
= 2\frac{w(e_{j})}{n − a − w(e_{j})},

where the first inequality is the triangle inequality, the second inequality follows from substituting in Z ⩽ \binom{n−a}{k−h} and Z − Z′ ⩽ \binom{n−a−1}{k−h−1}.

We have ∑ w(e_{j}) ⩽ Δ(n − a − 1), where the sum is over all hyperedges that contain a vertex greater than a + 1, as each vertex has degree at most Δ. Hence, the sum of |X_{a}(e_{j}) − X_{a+1}(e_{j})| over all vertices that contain a vertex greater than a + 1 is at most

2 ∑ \frac{w(e_{j})}{n − a − w(e_{j})} ⩽ 2Δk,

where we used (16). Putting this altogether, we have |Y_{a+1} − Y_{a}| ⩽ Δ(2k + 1). By Azuma’s inequality (15), the probability that Y_{n} = Y = m_{f} differs from X_{0} = |E(H)| · |E(F)|/\binom{n}{k} by

more than λ\sqrt{n} is at most 2e^{− \frac{λ^{2}}{2(2k+1)^{2}Δ^{2}}} . □

We use the following well known fact (see [30], pp. 43–52).

Lemma 9.3. Any set P of n points in ℝ^{d} determine at most n^{d^{2}} regions, such that any two points in the same region are in the same collection of simplices with vertices in P.

The two previous lemmas are all the tools we need to complete the proof of Theorem 9.1.

Proof of Theorem 9.1: Since H does not have isolated vertices, the number |E(H)| of hyperedges of H is at least n/(d + 1). Let P be a set of n points in ℝ^{d} such that no point q ∈ ℝ^{d} is in more than a fraction c of the simplices whose vertices are in P. By Lemma 9.3, P determines at most n^{d^{2}} regions, such that any two points in the same region are in the same collection of simplices with vertices in P. Let q be a representative point for a region, c_{q} ⩽ c denote the fraction of simplices with vertices in P that contain q, and let F_{q} denote the hypergraph on P consisting of all simplices with vertices in P that contain the point q.

Let f : V (H) → P be a bijection taken uniformly at random. By Lemma 9.2, the probability that the fraction of hyperedges of H which map to simplices containing q is at

least c_{q} + ε is at most 2e^{− \frac{λ^{2}}{2(2d+3)^{2}Δ^{2}}} , where λ\sqrt{n} = ε|E(H)| ⩾ εn/(d + 1). However, there are at most n^{d^{2}} such hypergraphs F_{q}, and since n ⩾ 2^{9}ε^{−3}d^{9}Δ^{3}, the probability is at most

n^{d^{2}}e^{− \frac{λ^{2}}{2(2d+3)^{2}Δ^{2}}} ⩽ exp (d^{2} log n − \frac{(ε\sqrt{n}/(d + 1))^{2}}{2(2d + 3)^{2}Δ^{2}} ) ⩽ exp (d^{2} log n − \frac{ε^{2}n}{2(2d + 3)^{4}Δ^{2}} ) = o(1)

that there is a point in ℝ^{d} contained in more than a fraction c + ε of the hyperedges of H. Thus, with high probability, a uniformly random bijection has the desired property. □

10. Concluding remarks

An alternative proof of Theorem 1.3 was given by Gromov [17], based on an application of Garland’s vanishing theorem to finite quotients of certain Bruhat-Tits building. Gromov’s argument fails for d > 2, and does not yield the sharp constant \frac{2}{9} as in Theorem 1.3, yet his construction has some remarkable stronger properties which we now describe.

Gromov investigated [17] the role of the fact that the edges of the triangles in the Boros-Füredi theorem are assumed to be straight line segments. He showed that it suffices to replace “straight lines” by sufficiently regular Jordan arcs. Gromov’s construction based on Garland’s theorem enjoys this stronger property as well (see Section 2.10 in [17]): one just needs the associated mapping from Gromov’s simplicial complex to ℝ^{2} to be continuous, the image of each edge to be nowhere dense in ℝ^{2}, and that its restriction to each face is at most r-to-1 (in which case the resulting bounds depend on r). At present it is unknown whether for d ⩾ 3 there exist arbitrarily large bounded degree d-dimensional simplicial complexes which are highly overlapping with respect to non-affine embeddings into ℝ^{d}.

An inspection of the construction of Section 4.2 reveals that, if the graph G has girth greater than 2d, then the resulting bounded degree d-dimensional highly overlapping simplicial complexes admit a continuous and piecewise affine retraction onto their 1-skeleton. It follows that for these complexes, if we replace “simplices” by “generalized simplices” whose edges are allowed to be continuous and piecewise affine arcs rather than straight lines, then the conclusion that there must be a point in a constant fraction of these generalized simplices, corresponding to an embedding of their vertex set into ℝ^{d}, would fail. Thus, the situation in the sparse setting is subtle, and passing from the case of affine mapping to more general continuous mappings is not automatic.

It follows for instance from [4] and [27] that for any system of at least constant times n^{3} triangles induced by a set of n points in the plane in general position, there is a point covered by at least a positive fraction of all triangles. In the present paper, we studied sparse systems of triangles with similar properties. Another closely related question is the following. For any positive integers n and 1 < t < \binom{n}{3}, determine the largest number m such that for any system of at least t triangles induced by a set of n points in the plane, there is a point contained in at least m triangles. See [2], [25]. The best known general lower bound is roughly t^{3}/n^{6}, but for most values of the parameters this is probably a very weak bound.

Acknowledgements. We thank Gábor Tardos for many useful conversations and ideas, and Yves Benoist for his help on Section 5.

References

[1] N. Alon and J. H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., Hoboken, NJ, third edition, 2008. With an appendix on the life and work of Paul Erdős.

[2] B. Aronov, B. Chazelle, H. Edelsbrunner, L. J. Guibas, M. Sharir, and R. Wenger. Points and triangles in the plane and halving planes in space. Discrete Comput. Geom., 6(5):435–442, 1991.

[3] C. M. Ballantine. Ramanujan type buildings. Canad. J. Math., 52(6):1121–1148, 2000.

[4] I. Bárány. A generalization of Carathéodory’s theorem. Discrete Math., 40(2-3):141–152, 1982.

[5] B. Bekka, P. de la Harpe, and A. Valette. Kazhdan’s property (T), volume 11 of New Mathematical Monographs. Cambridge University Press, Cambridge, 2008.

[6] Y. Benoist. Five lectures on lattices in semisimple Lie groups. 2004. To appear in the collection “Séminaires et congrès” of the SMF. Preprint available at

http://www.math.u-psud.fr/~benoist/prepubli/04lattice.pdf.

[7] A. Borel and G. Harder. Existence of discrete cocompact subgroups of reductive groups over local fields. J. Reine Angew. Math., 298:53–64, 1978.

[8] E. Boros and Z. Füredi. The number of triangles covering the center of an n-set. Geom. Dedicata, 17(1):69–77, 1984.

[9] B. Bukh. A point in many triangles. Electron. J. Combin., 13(1):Note 10, 3 pp. (electronic), 2006.

[10] B. Bukh, J. Matoušek, and G. Nivasch. Stabbing simplices by points and flats. 2006. Preprint availabel at arXiv:0804.4464, to appear in Discrete Comput. Geom.

[11] D. I. Cartwright, P. Solé, and A. Żuk. Ramanujan geometries of type Ã_{n}. Discrete Math., 269(1-3):35–43, 2003.

[12] D. I. Cartwright and T. Steger. A family of Ã_{n}-groups. Israel J. Math., 103:125–140, 1998.

[13] J. G. Ceder. Generalized sixpartite problems. Bol. Soc. Mat. Mexicana (2), 9:28–32, 1964.

[14] G. Davidoff, P. Sarnak, and A. Valette. Elementary number theory, group theory, and Ramanujan graphs, volume 55 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 2003.

[15] D. Dubhashi and D. Ranjan. Balls and bins: a study in negative dependence. Random Structures Algorithms, 13(2):99–124, 1998.

[16] J. Eckhoff. Helly, Radon, and Carathéodory type theorems. In Handbook of convex geometry, Vol. A, B, pages 389–448. North-Holland, Amsterdam, 1993.

[17] M. Gromov. Singularities, expanders and topology of maps, part 2: From combinatorics to topology via algebraic isoperimetry. 2008. To appear in Geom. Funct. Anal.

[18] S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.), 43(4):439–561 (electronic), 2006.

[19] W.-C. W. Li. Ramanujan hypergraphs. Geom. Funct. Anal., 14(2):380–399, 2004.

[20] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.

[21] A. Lubotzky, B. Samuels, and U. Vishne. Explicit constructions of Ramanujan complexes of type Ã_{d}. European J. Combin., 26(6):965–993, 2005.

[22] A. Lubotzky, B. Samuels, and U. Vishne. Ramanujan complexes of type Ã_{d}. Israel J. Math., 149:267– 299, 2005. Probability in mathematics.

[23] G. A. Margulis. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51–60, 1988.

[24] J. Matoušek. Using the Borsuk-Ulam theorem. Universitext. Springer-Verlag, Berlin, 2003. Lectures on topological methods in combinatorics and geometry, Written in cooperation with Anders Björner and Günter M. Ziegler.

[25] G. Nivasch and M. Sharir. Eppstein’s bound on intersecting triangles revisited. J. Combin. Theory Ser. A, 116(2):494–497, 2009.

[26] H. Oh. Uniform pointwise bounds for matrix coefficients of unitary representations and applications to Kazhdan constants. Duke Math. J., 113(1):133–192, 2002.

[27] J. Pach. A Tverberg-type result on multicolored simplices. Comput. Geom., 10(2):71–76, 1998.

[28] J. Pach and J. Solymosi. Structure theorems for systems of segments. In Discrete and computational geometry (Tokyo, 2000), volume 2098 of Lecture Notes in Comput. Sci., pages 308–317. Springer, Berlin, 2001.

[29] M. S. Pinsker. On the complexity of a concentrator. In 7th International Telegraffic Conference, pages 318/1–318/4. 1973.

[30] G. Polya. Induction and analogy in mathematics. Mathematics and plausible reasoning, vol. I. Princeton University Press, Princeton, N. J., 1954.

[31] A. Sarveniazi. Explicit construction of a Ramanujan (n_{1}, n_{2}, …, n_{d−1})-regular hypergraph. Duke Math. J., 139(1):141–171, 2007.

[32] W. Sierpiński. Sur les fonctions d’ensemble additives et continues. Fund. Math., 3:240–246, 1922.

[33] T. Steger. Local fields and buildings. In Harmonic functions on trees and buildings (New York, 1995), volume 206 of Contemp. Math., pages 79–107. Amer. Math. Soc., Providence, RI, 1997.

Jacob Fox: Department of Mathematics, Princeton University. Email: jacobfox@math.princeton.edu. Research supported by an NSF Graduate Research Fellowship and a Princeton Centennial Fellowship.

Mikhail Gromov: IHES and Courant Institute, NYU. Email: gromov@cims.nyu.edu.

Vincent Lafforgue: CNRS, Université Paris 7 Denis Diderot. Email: vlafforg@math.jussieu.fr.

Assaf Naor: Courant Institute, NYU. Email: naor@cims.nyu.edu. Research supported by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation.

János Pach: EPFL, CUNY, and Courant Institute, NYU. Email: pach@cims.nyu.edu. Supported by NSF Grant CCF-08-30272, and by grants from NSA, PSC-CUNY, the Hungarian Research Foundation OTKA, and BSF.