A TVERBERG-TYPE RESULT ON MULTICOLORED SIMPLICES

JÁNOS PACH

Abstract. Let P_{1}, P_{2}, …, P_{d+1} be pairwise disjoint n-element point sets in general position in d-space. It is shown that there exist a point O and suitable subsets Q_{i} ⊆ P_{i} (i = 1, 2, …, d + 1) such that |Q_{i}| ≥ c_{d}|P_{i}|, and every d-dimensional simplex with exactly one vertex in each Q_{i} contains O in its interior. Here c_{d} is a positive constant depending only on d.

1. Introduction

Let P_{1}, P_{2}, …, P_{d+1} be pairwise disjoint n-element point sets in general position in Euclidean d-space ℜ^{d}. If two points belong to the same P_{i}, then we say that they are of the same color. A d-dimensional simplex is called multicolored, if it has exactly one vertex in each P_{i} (i = 1, 2, …, d + 1). Answering a question of Bárány, Füredi, and Lovász [BFL90], Vrećica and Živaljević [ZV92], proved the following Tverberg-type result. For every k, there exists an integer n(k, d) such that if n ≥ n(k, d), then one can always find k multicolored vertex disjoint simplices with an interior point in common. (For some special cases, see [BL92], [JS91], [VZ94].) This theorem can be used to derive a nontrivial upper bound on the number of different ways one can cut a finite point set into two (roughly) equal halves by a hyperplane.

The aim of this note is to strengthen the above result by showing that there exist “large” subsets of the sets P_{i} such that all multicolored simplices induced by them have an interior point in common.

Theorem. There exists c_{d} > 0 with the property that for any disjoint n-element point sets P_{1}, P_{2}, …, P_{d+1} ⊂ ℜ^{d} in general position, one can find a point O and suitable subsets Q_{i} ⊆ P_{i}, |Q_{i}| ≥ c_{d}|P_{i}| (i = 1, 2, …, d + 1) such that every ddimensional simplex with exactly one vertex in each Q_{i} contains O in its interior.

The proof is based on the k = d + 1 special case of the Vrećica-Živaljević theorem (see Theorem 2.1). It uses three auxiliary results, each of them interesting on its own right. The first is Kalai’s fractional Helly theorem [K84], which sharpens and generalizes some earlier results of Katchalski and Liu [KL79] (see Theorem 2.2). The second is a variation of Szemerédi’s regularity lemma for hypergraphs [S78] (Theorem 2.3), and the third is a corollary of Radon’s theorem [R21], discovered and applied by Goodman and Pollack [GPW96] (Theorem 2.4).

Supported by NSF grant CCR-94-24398, PSC-CUNY Research Award 663472 and OTKA-4269.

This paper was written while the author was visiting MSRI Berkeley, as part of the Convex Geometry Program. Research at MSRI is supported in part by NSF grant DMS-9022140.

In the next section, we state the above mentioned results and also include a short proof of Theorem 2.3, because in its present form it cannot be found in the literature. Our argument is an adaptation of the approach of Komlós and Sós [KS96]. For some similar results, see [C91],[FR92],[KS95]. The proof of the Theorem is given in Section 3. It shows that the statement is true for a constant c_{d} > 0 whose value is tripleexponentially decreasing in d.

2. Auxiliary results

Theorem 2.1. [ZV92] Let A_{1}, A_{2}, …, A_{d+1} be disjoint 4d-element sets in general position in d-space. Then one can find d + 1 vertex disjoint simplices with a common interior point such that each of them has exactly one vertex in every A_{i}, 1 ≤ i ≤ d+1.

A family of sets is called intersecting if they have an element in common.

Theorem 2.2. [K84] For any α > 0, there exists β = β(α, d) > 0 satisfying the following condition. Any family of N convex sets in d-space, which contains at least α\binom{N}{d+1} intersecting (d + 1)-tuples, has an intersecting subfamily with at least βN members.

In fact, if N is sufficiently large, then Theorem 2.2 is true for any β < 1 − (1 − α)^{1/(d+1)}. In particular, it holds for β = α/(d + 1).

Let H be a (d+1)-partite hypergraph whose vertex set is the union of d+1 pairwise disjoint n-element sets, P_{1}, P_{2}, …, P_{d+1}, and whose edges are (d+1)-tuples containing precisely one element from each P_{i}. For any subsets S_{i} ⊆ P_{i} (1 ≤ i ≤ d + 1), let e(S_{1}, …, S_{d+1}) denote the number of edges of H induced by S_{1} ∪ … ∪ S_{d+1}. In this notation, the total number of edges of H is equal to e(P_{1}, …, P_{d+1}).

It is not hard to see that for any sets S_{i} and for any integers t_{i} ≤ |S_{i}|, 1 ≤ i ≤ d+1,

\frac{e(S_{1}, …, S_{d+1})}{|S_{1}| … |S_{d+1}|} = ∑ \frac{e(T_{1}, …, T_{d+1})}{|T_{1}| … |T_{d+1}|}/\binom{|S_{1}|}{t_{1}} … \binom{|S_{d+1}|}{t_{d+1}},  (1)

where the sum is taken over all t_{i}-element subsets T_{i} ⊆ S_{i}, 1 ≤ i ≤ d + 1.

Theorem 2.3. Let H be a (d + 1)-partite hypergraph on the vertex set P_{1} ∪ … ∪ P_{d+1}, |P_{i}| = n (1 ≤ i ≤ d + 1), and assume that H has at least βn^{d+1} edges for some β > 0. Let 0 < ε < 1/2.

Then there exist subsets S_{i} ⊆ P_{i} of equal size |S_{i}| = s ≥ β^{1/ε^{2d}}n (1 ≤ i ≤ d + 1) such that

(i) e(S_{1}, …, S_{d+1}) ≥ βs^{d+1}, (ii) e(Q_{1}, …, Q_{d+1}) > 0 for any Q_{i} ⊆ S_{i} with |Q_{i}| ≥ εs (1 ≤ i ≤ d + 1).

Proof: Let S_{i} ⊆ P_{i} (1 ≤ i ≤ d + 1) be sets of equal size such that

\frac{e(S_{1}, …, S_{d+1})}{|S_{1}|^{d+1−ε^{2d}}}

is maximum, and denote |S_{1}| = … = |S_{d+1}| by s.

For this choice of S_{i}, condition (i) in the theorem is obviously satisfied, because

\frac{e(S_{1}, …, S_{d+1})}{|S_{1}|^{d+1−ε^{2d}}} ≥ \frac{e(P_{1}, …, P_{d+1})}{n^{d+1−ε^{2d}}} = \frac{β}{n^{−ε^{2d}}} ≥ \frac{β}{s^{−ε^{2d}}} .

Taking into account the trivial relation

\frac{e(S_{1}, …, S_{d+1})}{|S_{1}|^{d+1−ε^{2d}}} ≤ s^{ε^{2d}},

the above inequalities also yield that s ≥ β^{1/ε^{2d}}n.

It remains to verify (ii). To simplify the notation, assume that εs is an integer, and let Q_{i} be any εs-element subset of S_{i} (1 ≤ i ≤ d + 1). Then

e(Q_{1}, …, Q_{d+1}) = e(S_{1}, …, S_{d+1})
−e(S_{1} − Q_{1}, S_{2}, S_{3}, ..., S_{d+1})
−e(Q_{1}, S_{2} − Q_{2}, S_{3}, ..., S_{d+1})
−e(Q_{1}, Q_{2}, S_{3} − Q_{3}, ..., S_{d+1})
…
−e(Q_{1}, Q_{2}, Q_{3}, ..., S_{d+1} − Q_{d+1}).

In view of (1), it follows from the maximal choice of S_{i} that

e(S_{1} − Q_{1}, S_{2}, ..., S_{d+1})

= (1 − ε)s^{d+1} \frac{e(S_{1} − Q_{1}, S_{2}, ..., S_{d+1})}{|S_{1} − Q_{1}||S_{2}|...|S_{d+1}|}

= (1 − ε)s^{d+1} ∑_{{T_{i}⊆S_{i},|T_{i}|=(1−ε)s \atop 2≤i≤d+1}} \frac{e(S_{1} − Q_{1}, T_{2}, ..., T_{d+1})}{[(1 − ε)s]^{d+1}}/\binom{s}{εs}^{d}

≤ (1 − ε)s^{d+1} \frac{e(S_{1}, S_{2}, ..., S_{d+1})}{s^{d+1−ε^{2d}}}[(1 − ε)s]^{−ε^{2d}}

= e(S_{1}, ..., S_{d+1})(1 − ε)^{1−ε^{2d}}.

Similarly, for any i, 2 ≤ i ≤ d + 1, we have

e(Q_{1}, ..., Q_{i−1}, S_{i} − Q_{i}, S_{i+1}, ..., S_{d+1})
≤ e(S_{1}, ..., S_{d+1})ε^{i−1−ε^{2d}}(1 − ε).

Summing up these inequalities, we obtain

e(Q_{1}, …, Q_{d+1}) ≥ e(S_{1}, …, S_{d+1})(1 − (1 − ε)^{1−ε^{2d}} − ∑_{i=2}^{d+1} ε^{i−1−ε^{2d}}(1 − ε))

≥ e(S_{1}, …, S_{d+1})(1 − (1 − ε)^{1−ε^{2d}} − ε^{1−ε^{2d}} + ε^{d+1−ε^{2d}}) > 0,

as required. □

A (d + 1)-tuple of convex sets in d-space is called separated if any j of them can be strictly separated from the remaining d + 1 − j by a hyperplane, 1 ≤ j ≤ d. An arbitrary family of at least d + 1 convex sets in d-space is separated if every (d + 1)-tuple of it is separated.

Theorem 2.4. [GPW96] A family of convex sets in d-space is separated if and only if no d + 1 of its members can be intersected by a hyperplane.

Let n ≥ d + 1. Two sequences of points in d-space, (p_{1}, …, p_{n}) and (q_{1}, …, q_{n}), are said to have the same order type if for any integers 1 ≤ i_{1} < … < i_{d+1} ≤ n, the simplices p_{i_{1}} … p_{i_{d+1}} and q_{i_{1}} … q_{i_{d+1}} have the same orientation [GP93]. It readily follows from the last result that if C_{1}, …, C_{n} form a separated family of convex sets, then the order type of (p_{1}, …, p_{n}) will be the same for every choice of elements p_{i} ∈ C_{i}, 1 ≤ i ≤ n.

3. Proof of Theorem

Let P_{1}, …, P_{d+1} be pairwise disjoint n-element point sets in general position in d-space. If a simplex has precisely one vertex in each P_{i}, we call it multicolored. The number of multicolored simplices is N = n^{d+1}.

By Theorem 2.1, any collection of 4d-element subsets A_{i} ⊆ P_{i}, 1 ≤ i ≤ d + 1, induce d + 1 vertex disjoint multicolored simplices with a common interior point. Thus, the total number of intersecting (d + 1)-tuples of multicolored simplices is at least

\begin{matrix}\binom{n}{4d} & d+1 \\ \binom{n−d−1}{3d−1} & d+1 \end{matrix} > \frac{1}{(5d)^{d^{2}}} \binom{N}{d + 1}.

Hence, we can apply Theorem 2.2 with α = 1/(5d)^{d^{2}}. We obtain that there is a point O contained in the interior of at least βN = β(1/(5d)^{d^{2}}, d)n^{d+1} multicolored simplices.

Let H denote the (d+1)-partite hypergraph on the vertex set P_{1}∪…∪P_{d+1}, whose edge set consists of all multicolored (d + 1)-tuples that induce a simplex containing O in its interior.

Set ε = 1/2^{d2^{d}}, and apply Theorem 2.3 to the hypergraph H to find S_{i} ⊆ P_{i}, 1 ≤ i ≤ d + 1, meeting the requirements. By throwing out some points from each S_{i}, but retaining a positive proportion of them, we can achieve that the convex hulls of the sets S_{i} are separated. Indeed, assume e.g. that there is no hyperplane strictly separating S_{1} ∪ … ∪ S_{j} from S_{j+1} ∪ … ∪ S_{d+1}. By the ham-sandwich theorem [B33], one can find a hyperplane h which simultaneously bisects S_{1}, …, S_{d} into as equal parts as possible. Assume without loss of generality that at least half of the elements of S_{d+1} are “above” h. Then throw away all elements of S_{1} ∪…∪S_{j} that are above h and all elements of S_{j+1} ∪ … ∪ S_{d+1} that are below h. We can repeat this procedure as long as we find a non-separated (d + 1)-tuple. In each step, we reduce the size of every set by a factor of at most 2.

Notice that in the same manner we can also achieve that e.g. the (d + 1)-tuple {{O}, conv(S_{1}), …, conv(S_{d})} becomes separated. In this case, h will always pass through the point O, therefore O will never be deleted.

After at most (d + 2)2^{d} steps we end up with Q_{i} ⊆ S_{i}, |Q_{i}| > εs (1 ≤ i ≤ d + 1) such that {{O}, conv(S_{1}), …,conv(S_{d+1})} is a separated family. It follows from the remark after Theorem 2.4 that there are only two possibilities: either every multicolored simplex induced by Q_{1} ∪ … ∪ Q_{d+1} contains O in its interior, or none of them does. However, this latter option is ruled out by part (ii) of Theorem 2.3. This completes proof. □

Instead of applying Theorem 2.2, we could have started the proof by referring to the following result of Alon, Bárány, Füredi, and Kleitman [ABFK92], which is also based on Theorem 2.1. For any β > 0 there is a βd^{′} > 0 such that any family of βn^{d+1} simplices induced by n points in d-space has at least βd^{′}n^{d+1} members with non-empty intersection.

Our proof easily yields the following.

Theorem 3.1. For any β > 0 there is a βd^{′′} > 0 with the property that given any family of βn^{d+1} simplices induced by an n-element set P ⊂ ℜ^{d}, one can find a point O and suitable subsets Q_{i} ⊆ P_{i}, |Q_{i}| ≥ βd^{′′}|P_{i}| (i = 1, 2, …, d + 1) such that every d-dimensional simplex with exactly one vertex in each Q_{i} contains O.

Acknowledgement. I am grateful to Imre Bárány, Géza Tóth, and Pavel Valtr for their valuable suggestions.

References

[ABFK92] N. Alon, I. Bárány, Z. Füredi, and D. Kleitman, Point selections and weak ε-nets for convex hulls Combin. Probab. Comput. 1, 189–200.

[BFL90] I. Bárány, Z. Füredi, and L. Lovász, On the number of halving planes, Combinatorica 10, 175–183.

[BL92] I. Bárány and D. Larman, A colored version of Tverberg’s theorem, J. London Math. Soc. (2) 45, 314–320.

[B33] K. Borsuk, Drei Sätze über die n-dimensionale euklidische sphäre, Fundamenta Math. 20, 177–190.

[C91] F. R. K. Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Structures and Algorithms 2, 241–252.

[FR92] P. Frankl and V. Rödl, The uniformity lemma for hypergraphs, Graphs and Combinatorics 8, 309–312.

[GPW93] J. E. Goodman, R. Pollack, and R. Wenger, Geometric transversal theory, in: New Trends in Discrete and Computational Geometry (J. Pach, ed.), Springer-Verlag, Berlin, 163–198.

[GPW96] J. E. Goodman, R. Pollack, and R. Wenger, Bounding the number of geometric permutations induced by k-transversals, J. Combin. Theory, Ser. A, to appear.

[JS91] J. Jaromczyk and G. Światek, The optimal constant for the colored version of Tverberg’s theorem, manuscript.

[K84] G. Kalai, Intersection patterns of convex sets, Israel J. Math. 48, 161–174.

[KL79] M. Katchalski and A. Liu, A problem of geometry in ℜ^{d}, Proc. Amer. Math. Soc. 75, 284–288.

[KS95] J. Komlós and M. Simonovits, Szemerédi’s regularity lemma and its applications, to appear in: Paul Erdős is Eighty, Proc. Colloq. Math. Soc. J. Bolyai.

[KS96] J. Komlós and V. T. Sós, Regular subgraphs of graphs, manuscript.

[R21] J. Radon, Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten, Math. Ann. 83, 113–115.

[S78] E. Szemerédi, Regular partitions of graphs, in: Problèmes combinatoires et théorie des graphes, Colloq. Internat. CNRS 260, CNRS, Paris, 399–401.

[T66] H. Tverberg, A generalization of Radon’s theorem, J. London Math. Soc. 41, 123–128.

[VZ94] S. T. Vrećica and R. T. Živaljević, New cases of the colored Tverberg theorem, in: Jerusalem Combinatorics ’93, Contemp. Math. 178, Amer. Math. Soc., Providence, 325–334.

[ZV92] R. T. Živaljević and S. T. Vrećica, The colored Tverberg’s problem and complexes of injective functions, J. Combin. Theory Ser. A 61, 309–318.

János Pach, City College, CUNY and, Courant Institute, NYU, 251 Mercer Street, New York, NY 10012

  E-mail address: pachcims6.nyu.edu