A Note on the Tolerant Tverberg Theorem

Abstract

The tolerant Tverberg theorem generalizes Tverberg’s theorem by introducing a new parameter t called tolerance. It states that there is a minimal number N so that any set of at least N points in $\mathbb R^d$ can be partitioned into r disjoint sets such that they remain intersecting even after removing any t points from X. In this paper we give an asymptotically tight bound for the tolerant Tverberg Theorem when the dimension and the size of the partition are fixed. To achieve this, we study certain partitions of order-type homogeneous sets and use a generalization of the Erdős–Szekeres theorem. As far as we know, this is the first time that a Ramsey-type theorem has been used to prove a Tverberg-type result.

1 Introduction

Tverberg’s theorem [18] states that any set with at least $(d+1)(r-1)+1$ points in $\mathbb R^d$ can be partitioned into r disjoint sets $A_1, \ldots , A_r$ such that $\bigcap _{i=1}^r {{\mathrm{conv}}}(A_i) \ne \emptyset$. Furthermore, this bound is tight. For a gentle introduction to this theorem and some of its relatives see [11, Chap. 8].

The tolerant Tverberg theorem generalizes Tverberg’s theorem by introducing a new parameter t called tolerance. It states that there is a minimal number $N=N(d,t,r)$ so that any set X of at least N points in $\mathbb R^d$ can be partitioned into r disjoint sets $A_1, \ldots , A_r$ such that $\bigcap _{i=1}^r {{\mathrm{conv}}}(A_i{\setminus } Y) \ne \emptyset$ for any $Y\subset X$ with at most t points.

In contrast with the classical Tverberg theorem, the best known bounds for N(d, t, r) are not tight. Larman [10] proved that $N(d,1,2)\le 2d+3,$ García-Colín showed that $N(d,t,2)\le (t+1)(d+1)+1$ in her PhD thesis [7], later published in [8]. This was later generalized by Strausz and Soberón who gave the general bound $N(d,t,r)\le (r-1)(t+1)(d+1)+1$ [16]. Later, Mulzer and Stein gave the bound $N(d,t,r)\le 2^{d-1}(r(t+2)-1)$ which improves the previous bound for $d\le 2$ and is tight for $d=1$ [13].

As for lower bounds, Ramírez-Alfonsín [14] and García-Colín [8], using oriented matroids, proved that $\lceil {\frac{5d}{3}}\rceil +3 \le N{(d, 1, 2)}$ and $2d + t +1 \le N{(d, t, 2)},$ respectively. Furthermore, Larman’s upper bound is known to be sharp for $d=1, 2, 3$ and 4 [5, 10]. Lastly, Soberón gave the bound $r(\lfloor {\frac{d}{2}}\rfloor +t+1)\le N(d,t,r)$ [15].

In this paper we show that for fixed d and r, the correct value for N(d, t, r) is asymptotically equal to rt. To be precise, we prove the following theorem.

Theorem 1.1

For fixed r and d we have that

$$\begin{aligned} N(d,t,r) = rt + o(t). \end{aligned}$$

This improves all previously known upper bounds whenever t is large compared to r and d, and comes with a matching lower bound.

The proof follows from studying the behavior of t with respect to N and using a generalization of the Erdős–Szekeres theorem for cyclic polytopes in $\mathbb R^d$. We include a short review of cyclic polytopes and this theorem in Sect. 2. As far as we know, this is the first time that a Ramsey-type result, such as this generalization of the Erdős–Szekeres theorem, has been used to prove a Tverberg-type theorem. In Sect. 3.1 we prove a useful lemma about alternating partitions of a cyclic polytope which leads to an interesting open problem. The proof of Theorem 1.1 is detailed in Sect. 4.

2 Preliminaries

In this section we introduce some definitions and recall some well-known concepts which we later use in the proofs of this paper.

2.1 Order-Type Homogeneous Sets

Any ordered set of points $X \subset \mathbb R^d$ with the property that the orientation of any ordered subset of X with $d+1$ elements is always the same is called an order-type homogeneous set.

A classic example of such a set is the set of vertices of a cyclic polytope, X, which is constructed as follows: consider the moment curve $\gamma (\alpha )=(\alpha , \alpha ^2, \ldots , \alpha ^d)$, given real numbers $\alpha _1<\alpha _2<\cdots <\alpha _n$, define $X=\{\gamma (\alpha _1),\gamma (\alpha _2),\ldots ,\gamma (\alpha _n)\}.$ The set ${{\mathrm{conv}}}(X)$ is the d-dimensional cyclic polytope on n points and any other polytope combinatorially equivalent to the cyclic polytope is also sometimes referred to as a cyclic polytope or, more generally, as an order-type homogeneous set.

Order-type homogeneous sets have been studied extensively [2, 6, 9, 11, 19] and have proven to be very effective in giving examples with extremal properties in various combinatorial problems. In our case they will prove useful in finding better bounds for the tolerant Tverberg number N(d, t, r).

The following lemma, due to Gale [6] is one of the most powerful tools for studying the properties of order-type homogeneous sets.

Lemma 2.1

(Gale’s evenness criterion) Let $X=\{x_1,x_2,\ldots ,x_n\}\subset \mathbb R^d$ be an order-type homogeneous set. A subset $F \subset X$ such that $|{F}|=d$ determines a facet of $\mathrm{conv}(X)$ if and only if, any two vertices in $X {\setminus } F$ have an even number of vertices of F between them in the order.

As a consequence of Lemma 2.1, the polytopes that arise as the convex hulls of order-type homogeneous sets are known to be $\lfloor {\frac{d}{2}}\rfloor$-neighborly. That is, the convex hull of every $\lfloor {\frac{d}{2}}\rfloor$ points in X is contained in a facet of C and, since C is simplicial, the convex hull of such vertices is a $\lfloor {\frac{d}{2}}\rfloor -1$ face of C.

Another useful fact when working with order-type homogeneous sets is [1, Lem. 2.1]. Recall that a set of points $X\subset \mathbb R^d$ is in general position if no $k+2$ points of X are contained in a k-dimensional subspace of $R^d$ for every $k\ge 0$.

Lemma 2.2

An ordered set $X=\{x_1,x_2,\ldots x_n\}$ in general position in $\mathbb R^d$ is order-type homogeneous if and only if the polygonal path $\pi =x_1x_2\ldots x_n$ intersects every hyperplane in at most d points, with the exception of the hyperplanes that contain an edge of $\pi$.

2.2 A Generalization of the Erdős–Szekeres Theorem

In 1935 Erdős and Szekeres proved two important theorems in combinatorial geometry [4]. The first Erdős–Szekeres theorem implies that any sequence of numbers with length $(n-1)^2+1$ always contains a monotone (either increasing or decreasing) subsequence. The second Erdős–Szekeres theorem states that among any $2^{\varTheta (n)}$ points in the plane there are n of them in convex position.

These two theorems can be thought of as results on order-type homogeneous sets in dimensions 1 and 2. The following theorem, whose upper bound was proved by Suk [17] and lower bound by Bárány et al. [1], generalizes both results to order-type homogeneous sets in any d-dimensional space.

Theorem 2.3

Let ${{\mathrm{OT}}}_d(n)$ be the smallest integer such that any set of ${{\mathrm{OT}}}_d(n)$ points in general position in $\mathbb R^d$ contains an order-type homogeneous subset of size n. Then ${{\mathrm{OT}}}_d(n)={{\mathrm{twr}}}_d(\varTheta (n))$, where the tower function ${{\mathrm{twr}}}_d$ is defined by ${{\mathrm{twr}}}_1(\alpha )=\alpha$ and ${{\mathrm{twr}}}_{i+1}(\alpha )=2^{{{\mathrm{twr}}}_i(\alpha )}$.

3 Tolerance of Partitions of Sets

Let $X=\{x_1,x_2,\ldots ,x_n\}$ be a set of points in $\mathbb R^d$. We define the tolerance t(X, r) of X as the maximum number of points such that there is a partition $A_1, \ldots , A_r$ of X with the property that $\bigcap _{i=1}^r {{\mathrm{conv}}}(A_i{\setminus } Y) \ne \emptyset$ for any $Y\subset X$ with at most t(X, r) points.

The following observation can be found as [13, Lem. 3.1].

Observation 3.1

Let $X_1$, $X_2$ be disjoint sets of points of $\mathbb R^d$. Then $t(X_1\cup X_2,r) \ge t(X_1,r)+t(X_2,r)+1$.

We also define the following two numbers

$$\begin{aligned} t(n, d, r)=\min _{\begin{array}{c} X \subset \mathbb R^d \\ |X|=n \end{array}}\{t(X,r)\} \quad \text { and } \quad T(n, d, r)=\max _{\begin{array}{c} X \subset \mathbb R^d \\ |X|=n \end{array}}\{t(X,r)\}, \end{aligned}$$

where the sets X are also required to be in general position.

The value t(n, d, r) indicates that for every set X of n points in general position there is a partition $A_1, \ldots , A_r$ of X such that $\bigcap _{i=1}^r {{\mathrm{conv}}}(A_i{\setminus } Y) \ne \emptyset$ for any $Y\subset X$ with at most $t(X,r)=t(n, d, r)$ points. Meanwhile, T(n, d, r) indicates that there exists a set X of n points in general position with a partition $A_1, \ldots , A_r$ such that $\bigcap _{i=1}^r {{\mathrm{conv}}}(A_i{\setminus } Y) \ne \emptyset$ for any $Y\subset X$ with at most $t(X,r)=T(n, d, r)$ points.

3.1 Tolerance of Order-Type Homogeneous Sets

In order to prove Theorem 1.1 we need to study a specific type of partitions. Let $X=\{x_1,x_2,\ldots ,x_n\}$ be an ordered set of points in $\mathbb R^d$ with the order specified by its indexes and let $r>0$ be a fixed integer. The partition of X into r sets $A_1, \ldots , A_r$ given by $A_i=\{x_j : j \equiv i \,\mathrm{mod}\, r\}$ is called the alternating partition. Our main interest is to determine when the convex hulls of the sets $A_i$ intersect and how tolerant they are, in the sense of how many points can be removed from the $A_i$’s so that their convex hulls are still intersecting.

Lemma 3.2

Let $X=\{x_1,x_2,\ldots ,x_n\}$ be an order-type homogeneous set of points in $\mathbb R^d$ with alternating partition $A_1, \ldots , A_r$. Then there is a number $c(d,r)\le (d\,{+}\,1)(\lfloor {\frac{d}{2}}\rfloor \,{+}\,1)(r-1)\,{+}\,1\approx \frac{rd^2}{2}$ such that, if $n\ge c(d,r)$, then $\bigcap _{i=1}^r {{\mathrm{conv}}}(A_i)\ne \emptyset$.

Fig. 1

An example for Lemma 3.2 with $n=14$, $d=6$ and $r=3$. The set $A_3$, in red, is to the left of H and the path $\pi$ intersects H at most d times

Proof

Let O be a center point for X. This means that every closed semi-space containing O also contains at least $\lceil {\frac{n}{d+1}}\rceil$ points of X. We will show that $O\in {{\mathrm{conv}}}(A_i)$ for every i. Suppose this is not the case. Then there is a hyperplane H strictly separating O from some ${{\mathrm{conv}}}(A_i)$. We may assume (by perturbing H if necessary) that no point in X is contained in H.

Let $H^+$ be the closed semi-space bounded by H that contains O. Since O is a center point then $X\cap H^+$ contains at least $\lceil {\frac{n}{d+1}}\rceil >(\lfloor {\frac{d}{2}}\rfloor +1)(r-1)$ points.

On the other hand, by Lemma 2.2, the polygonal path $\pi$ generated by X intersects H at most d times. Therefore $\pi \cap H^+$ has at most $\lfloor {\frac{d}{2}}\rfloor +1$ connected components and, since $A_i\cap H^+=\emptyset$, each of these components is a sub-path of $\pi$ contained between two consecutive points of $A_i\subset \pi$ (see Fig. 1). Thus, each component contains at most $r-1$ points from X, so $X\cap H^+$ has at most $(\lfloor {\frac{d}{2}}\rfloor +1)(r-1)$ points. This contradicts our assumption that $O\not \in {{\mathrm{conv}}}(A_i)$. $\square$

The bound for c(d, r) given in the previous lemma is not tight. In fact it can be improved when d is even by noticing that, if $n\equiv i$ (mod r), then $X\cap H^+$ can have at most $\frac{d}{2}(r-1)+i$ points. The bound obtained in this case is $c(d,r)\le \min _i \big \{\frac{d(d+1)}{2}(r-1)+i(d+1)+s_i\big \}$, where $s_i$ be the smallest positive integer such that $s_i\equiv \frac{d(d+1)}{2}-id$ (mod r). When r is large compared to d this simply equals $\frac{d(d+1)}{2}r$. However this bound is still not tight, giving rise to an interesting open question.

Problem 3.3

Determine the smallest value for c(d, r) for which Lemma 3.2 holds.

There are two easy cases in this problem. The first one is when $r=1$, then the partition contains only $A_1$, so we immediately have that $c(d,1)=1$. The other is when $d=1$, then the set X is an increasing sequence of real numbers and in this case it is easy to show that $c(1,r)=2r-1$.

The case $d=2$ is also not difficult. The first value $c(2,2)=4$ comes from the fact that the diagonals of a convex quadrilateral intersect. However, if $r\ge 3$ we have $c(2,r)=3r$ instead. To prove that $c(2,r)\le 3r$ it is enough, by Helly’s theorem, to show that $c(2,3)=9$. If this were not the case then there would be a line L separating ${{\mathrm{conv}}}(A_1)\cup {{\mathrm{conv}}}(A_2)$ from $A_3$, but since the partition is alternating ${{\mathrm{conv}}}(A_1)$ and ${{\mathrm{conv}}}(A_2)$ must intersect on the side of L containing $A_3$. In order to prove that $c(2,r)\ge 3r$, consider the example in Fig. 2.

Fig. 2

An example showing $c(2,r)\ge 3r$

If $r=2$, a simple separating-hyperplane argument using Lemma 2.2 shows that $c(d,2)=d+2$. In general, it can also be proved that $c(d,r)\ge (d+1)r$ whenever $r>d$, but this is also not tight. The following example shows that $c(3,4)>16$: Consider the four alternating tetrahedra with vertices on the moment curve $(t,t^2,t^3)$ when t takes the values $-4$, $-3$, $-2$, $-2$, $-2$, $-1$, $-1$, $-1$, 0, 1, 2, 6, 6, 7, 8 and 9. It can be shown that these tetrahedra do not have a common point. This example has small integer coordinates but some of the points are repeated, this can be avoided by slightly perturbing the values of t.

Now we are ready to study the tolerance of an order-type homogeneous set.

Theorem 3.4

Let $X=\{x_1,x_2,\ldots ,x_n\}$ be an order-type homogeneous set of points in $\mathbb R^d$. Then $\lfloor {\frac{n}{r}}\rfloor - \lceil \frac{c(d,r)}{r}\rceil \le t(X,r)$, where c(d, r) is the number from Lemma 3.2.

Proof

For the lower bound, consider the alternating partition $A_1, \ldots , A_r$ of X. Assume that $Y \subset X$ satisfies $|{Y}| \le \lfloor {\frac{n}{r}}\rfloor -\lceil \frac{c(d,r)}{r}\rceil$. Subdivide X into $\lfloor {\frac{n}{r}}\rfloor$ consecutive blocks of size r (ignoring the remaining points from X), then each block has exactly one point of each color. After removing Y from X, at least $\lceil \frac{c(d,r)}{r}\rceil$ blocks remain complete. Let $X'$ be the set containing the points from these blocks. Then $X'$ has at least c(d, r) points and the restriction of the partition of X to $X'$ (i.e. $A_1\cap X', \ldots , A_r \cap X'$) is also an alternating partition. Thus, by Lemma 3.2 we have that $\bigcap _{i=1}^r {{\mathrm{conv}}}(A_i \cap X') \ne \emptyset$ and the theorem follows. $\square$

An upper bound of $t(X,r)\le \lfloor {\frac{n}{r}}\rfloor -\lfloor {\frac{d}{2}}\rfloor$ was proved by Soberón in [15, Cla. 4.1], when X is an order-type homogeneous set in $\mathbb R^d$.

3.2 Tolerance of Partitions of General Sets

The bound $N(d,t,r)\le (r-1)(t+1)(d+1)+1$ for the tolerant Tverberg number implies that for any set X of n points, its tolerance is bounded by $\frac{n-1}{(r-1)(d+1)}-1 \le t(X, r).$ On the other hand, we can argue that the tolerance under any partition of a set can never be greater than the size of the smallest part in the partition, i.e. $T(n, d, r)\le \lfloor {\frac{n}{r}}\rfloor .$

The arguments in the previous paragraphs imply that $\frac{n-1}{(r-1)(d+1)}-1 \le t(n, d, r) \le t(X,r) \le T(n, d, r) \le \lfloor {\frac{n}{r}}\rfloor$ holds for any $X \subset \mathbb R^d$ with $|{X}|=n$.

In this section we exhibit improved bounds for the tolerance of partitions of general sets.

Proposition 3.5

For any positive integers n, d, r we have that $T(n,d,r)\le \lfloor {\frac{n}{r}}\rfloor -\lfloor {\frac{d}{2}}\rfloor$.

Proof

Let $X\subset \mathbb R^d$ be a set with n points in general position. Assume that $A_1, \ldots , A_r$ is a partition of X such that $\bigcap _{i=1}^r {{\mathrm{conv}}}(A_i{\setminus } Y) \ne \emptyset$ for any $Y\subset X$ with at most $T=T(n, d, r)$ points.

Let $A_i, A_j$ be parts such that $i \ne j$. We may assume that $|{A_i \cup A_j}|\ge d+2$, otherwise $T=0$. Then for any subset D of d points in $A_i \cup A_j$, the hyperplane $H={{\mathrm{aff}}}(D)$ divides $\mathbb R^d$ into two closed semi-spaces $H^+$ and $H^-$ so that $|{ H^+ \cap A_i}| + |{H^- \cap A_j}| >T$ and $|{H^- \cap A_i}| + |{H^+ \cap A_j}| >T$.

Hence $|{A_i}| + |{A_j}| -d > 2T$ and adding through all the different pairs, $\sum _{i<j} |{A_i}| + |{A_j}|> \left( {\begin{array}{c}r\\ 2\end{array}}\right) (2T+d)$. That is, $(r-1)\sum _{i \in [r]} |{A_i}| > \left( {\begin{array}{c}r\\ 2\end{array}}\right) (2T+d)$ and thus $n >\frac{r}{2}(2T+d)$. Rearranging the later equation we can obtain $\frac{n}{r}>T +\frac{d}{2}$. Therefore $\frac{n}{r}>T + \lfloor {\frac{d}{2}}\rfloor$ and so $\lfloor {\frac{n}{r}}\rfloor \ge T + \lfloor {\frac{d}{2}}\rfloor$. $\square$

Lemma 3.6

Let r, d be fixed natural numbers. For a large enough n we have that $t(n,d,r) \ge \frac{n}{r}-o(n)$.

Proof

Fix small $\varepsilon > 0$. We shall construct a large number n satisfying that, for any set X of n points in $\mathbb R^d$, we have $t(X,r) \ge \frac{n}{r}(1-\varepsilon )$. Let $c=c(d,r)$ be as in Lemma 3.2.

Assume that $n = {{\mathrm{OT}}}_d(k) + (m-1)k$ for some positive integers m and k, where ${{\mathrm{OT}}}_d$ is the bound from Theorem 2.3. Then, given a set X of n points in general position in $\mathbb R^d$, we can select m pairwise-disjoint order-type homogeneous subsets $X_1, X_2,\ldots , X_m$ of size k from X.

Partition the points of each $X_i$ into r parts using the alternating method proposed in Sect. 3.1. By Theorem 3.4, we have that $t(X_i,r) \ge \frac{k-c}{r}$ and therefore, by Observation 3.1, $t(X,r) \ge t(X_1,r)+\cdots +t(X_m,r) \ge m\big (\frac{k-c}{r}\big )$. We may rewrite this last value as

$$\begin{aligned} m\Big (\frac{k-c}{r}\Big )=\frac{n}{r}\Big (\frac{mk-mc}{n}\Big )=\frac{n}{r}\Big (1-\frac{{{\mathrm{OT}}}_d(k)+mc}{{{\mathrm{OT}}}_d(k)+mk}\Big ). \end{aligned}$$

By choosing a large enough k so that $\frac{1+c}{1+k} < \varepsilon$ and $m={{\mathrm{OT}}}_d(k)$, we obtain $t(X,r)\ge \frac{n}{r}\big (1-\frac{1+c}{1+k}\big )>\frac{n}{r}(1-\varepsilon )$. $\square$

A practical algorithm for finding highly tolerant colorings of a given set of points in $\mathbb {R}^d$ remains elusive. While the constructive nature of the above proof might seem to give an algorithm, a practical implementation would fail. Extracting an order-type homogeneous set from a given set of points is not a trivial task. Another problem is that the term $OT_d(k)$ is too large. For example, if we wanted an order-type homogeneous set of size k in dimension 3, we would need approximately $2^{2^k}$ points which is too large even for a relatively small k.

In the plane, however, one could construct a highly tolerant coloring of a given set of points by successively removing large convex sets and coloring them in an alternating fashion. There is an $O(N^3)$ dynamic programming algorithm for finding the convex set with the most points, given an initial set of points in the plane (see [3, Problem 4] and [12]).

4 Bounds on the Tolerant Tverberg Number

So far we have been concerned with studying the behavior of t with respect to n, d and r. By a simple manipulation of the results in the previous section, we may now easily prove Theorem 1.1.

Proof of Theorem 1.1 Fix r and d. By Proposition 3.5 we have that $t \le \lfloor {\frac{n}{r}}\rfloor -\lfloor {\frac{d}{2}}\rfloor$, which implies $n\ge tr+\frac{r(d-1)}{2}$. Lemma 3.6 can be rewritten as $n\le tr + o(n)$. These inequalities imply $n=\varTheta (t)$, so we have that

$$\begin{aligned} rt+\frac{r(d-1)}{2}\le n \le rt+ o(t), \end{aligned}$$

which yields the result. $\square$

This result clarifies why the search for a definite N(d, r, t) has been elusive. It seems that the relationship between t and N changes as t increases, as opposed to being a constant multiple of t (for a fixed d and r).

From the analysis made in Lemma 3.6 it follows that the term o(t) in Theorem 1.1 decays like $\frac{t}{\log ^{(d)}(t)}$, where $\log ^{(d)}$ represents the composition of d logarithm functions. This decay is extremely slow, it is our impression that N(d, t, r) approaches rt much faster than this.