CARATHÉODORY’S THEOREM,

COLOURFUL AND APPLICABLE

Imre Bárány,^{1} Mathematical Institute of the Hungarian Academy of Sciences, POBox 127, Budapest, 1364 Hungary, barany@math-inst.hu, and

Shmuel Onn,^{2} Department of Operations Research, School of Industrial Engineering and Management, Technion, 32000 Haifa, Israel, onn@ie.technion.ac.il

1. Introduction

What is usually termed ”Carathéodory’s theorem” is a very simple statement. It says that if A ⊂ R^{d} and a ∈ conv A (the convex hull of A), then there is a subset B of A of size at most d + 1 with a ∈ conv B. In other words, being in the convex hull has a ”simple” or ”finite” reason. Inspite of its simplicity, Carathédory’s theorem is very useful and has plenty of applications.

There is a multiplied, or colourful, version of Carathéodory’s theorem which was discovered in [B]. It has a lot of applications, some of them quite recent. The aim of this paper is to give a survey of this colourful version, its consequences, and some related ”colourful” results and open questions. We also want to direct attention to the algorithmic aspects that have come up.

2. The colourful version

The colourful version in the plane has an elementary form: Given a red, a white, and a green triangle, all of them containing the origin, there is a red vertex R, a white vertex W, and a green vertex G such that the multicoloured triangle RW G contains the origin. This elementary statement appeared as a problem in several popular mathematical journals [Kv, MI]. For the general form, let us introduce the following terminology. Given a family of sets (colours) A_{1}, …, A_{d+1} ⊂ R^{d}, a colourful set, or a choice is a set T = {a_{1}, …, a_{d+1}} where a_{i} ∈ A_{i} for all i.

Theorem 1. Assume A_{1}, …, A_{d+1} ⊂ R^{d} have a point a ∈ ∩_{1}^{d+1} conv A_{i} common to their convex hulls. Then there is a colourful set T = {a_{1}, …, a_{d+1}} containing a in its convex hull as well.

Theorem 1 reduces to the usual Carathéodory theorem when all the A_{i} are equal.

Typeset by AMS-TEX

1Partially supported by Hungarian National Science Foundation no. 4296 and 016937

2Partially supported by DIMACS, and by Technion VPR Fund 191–181 and 191–198

Of the several proofs available, the simplest is probably the following.

Proof. We may assume, by Carathéodory’s theorem, say, that every A_{i} is finite. Pick the colourful set T = {a_{1}, …, a_{d+1}} whose convex hull, C = conv T, is nearest to a. If a ∈ C, we are done, so suppose a ∉ C and let c be the point nearest to a in C. Now c is on the boundary of C so it can be written as a convex combination of at most d of the a_{i} (by Carathéodory’s theorem in R^{d−1}). Say, the first element, a_{1} is not used in the representation of c. Then a_{1} can be replaced by any element of A_{1} without increasing the distance between C and a. Moreover, the hyperplane H through c and orthogonal to a − c separates a from C. By the condition there is a b ∈ A_{1} on the same side of H as a_{1}. It is easy to see now that the convex hull of the colourful set T′ = {b, a_{2}, …, a_{d+1}} is nearer to a than C, a contradiction.

This proof can be turned into an algorithm which will be discussed in the next section. There is yet another (unpublished) proof which uses Tverberg’s method [T1] of moving the points.

The cone version of Carathéodory’s theorem admits a colourful variant, with identical proof. (Let pos A denote the cone hull of A ⊂ R^{d}.)

Theorem 2. Assume A_{1}, …, A_{d} ⊂ R^{d} and a ∈ ∩_{1}^{d} pos A_{i}. Then there is a colourful set T such that a is in pos T.

3. Algorithms and questions

To formulate the basic algorithmic question we assume a Turing machine computation model. We assume further that all elements of the sets A_{i} have rational coordinates. Then the size of the input is the usual one: the sum of the logarithms of the integers representing the rational numbers of the input.

Problem 1. Is there an algorithm that finds, in polynomial time in the size of the input, a colourful set whose existence is guaranteed by Theorem 1.

A positive answer would simply mean an effective algorithm. A negative answer, however, would mean a hardness result. Since the problem is a search problem and not a decison one, hardness for the class NP does not seem to be the right thing to look for. It may be more suitable to consider complexity theory of search problems as in [JPY], or to work within the complexity framework of non-approximable problems (the class MAXSNP of [PY]), for a certain associated approximation problem.

This approximation problem is studied in detail in a companion paper [BO], where some relatively efficient algorithms for it are given and analysed, and some hardness results of variants of Problem 1 are established. Problem 1 raises several other questions from what we like to call ”colourful linear algebra”. A detailed account of these questions and related results can be found in [BO].

We now outline an approximation algorithm for Problem 1. For the complete analysis we refer to [BO].

The proof of Theorem 1 is based on a ”pivot step” argument. Namely, given a colourful set T with a ∉ conv T, one can pivot out an element a_{i} ∈ A_{i} (for some i) and pivot in another element a′_{i} ∈ A_{i}, so that the convex hull of the new colourful set T′ = (T ∪ {a′_{i}}) \ {a_{i}} is nearer to a than conv T. This gives rise to the following algorithm.

Start with any colourful set T_{1}. On the kth iteration, check whether the colourful set T_{k} contains a in its convex hull. If it does, stop. Otherwise apply the pivot step to obtain the new colourful set T_{k+1} with dist(T_{k+1}, a) < dist(T_{k}, a).

This algorithm gives a sequence of colourful sets with strictly decreasing distances to a, so it surely terminates after ∏ |A_{i}| pivot steps producing a colourful set T with a ∈ conv T. So the algorithm is finite but the number of pivot steps may not be smaller than the total number of colourful sets.

However, the algorithm produces a ”good” approximation to the colourful set T with a ∈ conv T in the following sense. To simplify the discussion we assume a real arithmetic computational model. We assume further that the input is normalized as follows. First, a translation is applied so that the common point a becomes the origin. Second, each point is scaled to the unit sphere S^{d−1} ⊂ R^{d}. This does not affect whether 0 ∈ conv T for any subset T of the points.

Now let x_{k} denote the point, closest to the origin, of conv T_{k}, where T_{1}, T_{2}, … is the sequence of colourful sets given by the algorithm. A careful analysis (whose details appear in [BO]) shows that |x_{k}| ≤ k^{−1/2}. Or, to put it differently, in order to get a point x_{k} ∈ conv T_{k} within ε distance to the origin, it is enough to carry out ⌈ε^{−2}⌉ pivot steps. A more delicate analysis, under some assumptions, can in fact make the dependence on ε logarithmic. Details appear in [BO].

4. The colourful Helly theorem

László Lovász [L] proved a coloured version of Helly’s theorem (unpublished but see Problem no.206 in [ML] and also [B]) even before the discovery of the colourful Carathéodory theorem. We will see soon that the two results are in fact equivalent.

Theorem 3. Assume C_{1}, …, C_{d+1} are finite families of convex compact sets of R^{d} with the property that for every choice C_{1} ∈ C_{1}, …, C_{d+1} ∈ C_{d+1} the intersection ∩_{1}^{d+1}C_{i} is nonempty. Then for some i = 1, …, d + 1 the family C_{i} is intersecting.

When all families are equal, this is just Helly’s theorem.

We give here two proofs of the theorem. The first is similar to a proof of Helly’s theorem (like in Wegner [W], for instance). The second shows the equivalence of Theorems 2 and 3.

First proof. Call C_{i_{1}} ∈ C_{i_{1}}, …, C_{i_{d}} ∈ C_{i_{d}} a d-choice if 1 ≤ i_{1} < i_{2} < ⋯ < i_{d} ≤ d+1. Write F for the family of intersections of all d–choices. One can pick a vector v ∈ R^{d} such that for each F ∈ F, min{vx : x ∈ F } is reached at a unique point of F. Take the one, say F_{0}, for which this minimum is the largest; it is reached at x_{0} ∈ F_{0}. Without loss of generality we may take F_{0} = ∩_{1}^{d}C_{i}, so the last family is missing from F_{0}.

Claim. x_{0} ∈ C_{d+1} for every C_{d+1} ∈ C_{d+1}.

This will show that ∩C_{d+1} is nonempty. There are several ways to prove the claim. Here we choose one resembling the proof of Radon’s theorem [DGK]. Assume x_{0} ∉ C_{d+1} for some C_{d+1} ∈ C_{d+1}. Let y be the point where min{vx : x ∈ ∩_{1}^{d+1}C_{i}} is attained. As this set is nonempty, y is defined and vx_{0} < vy. Further, let x_{j} be the point for j = 1, …, d where the minimum of vx is reached in the set ∩_{j≠i}C_{j}. By the choice of x_{0}, vx_{j} ≤ vx_{0} for every j = 1, …, d. Thus the segments [x_{j}, y] intersect the hyperplane H = {x : vx = vx_{0}}, let y_{j} denote the point of intersection. Note that y_{j} ∈ C_{i} for all i = 1, …, d + 1 except j, this holds for y_{d+1} = x_{0} as well. Since this is a set of d + 1 points in H which is the (d − 1)–dimensional space there is a Radon partition (see [DGK]) of the set {y_{1}, …, y_{d+1}}; let z be the point common to the convex hull of the two parts. The usual argument shows that z ∈ ∩_{1}^{d+1}C_{i}. Now vz = vx_{0} < vy contradicting the choice of y.

Second proof. We need two well–known facts. First, compact convex sets K_{1}, …, K_{n} in R^{d} have no point in common if and only if there are closed halfspaces D_{1}, …, D_{n} such that K_{i} ⊂ D_{i} for every i and ∩D_{i} = ∅. When n = 2 this is the separation theorem, the general case follows by induction. The second thing we need is the Farkas lemma: let D_{i} be given by the inequality a_{i}x ≤ α_{i}. The halfspaces D_{1}, …, D_{n} have no point in common if and only if (0, −1) ∈ pos{(a_{i}, α_{i}) : i = 1, …, n}.

Now the proof of the theorem: If no C_{i} is intersecting, then there is a family D_{i} of closed halfspaces as specified above. Then, by the Farkas lemma, (0, −1) is in the cone hull of each set of vectors A_{i} = {(a, α) : ax ≤ α defines a halfspace in D_{i}}. There are d + 1 such sets (in R^{d+1}), so by Theorem 2, there is a choice (a_{i}, α_{i}) ∈ A_{i} with (0, −1) ∈ pos{(a_{i}, α_{i}) : i = 1, …, d + 1}. This means, in turn, that the intersection of the corresponding C_{i} ∈ C_{i} is empty, contradicting the condition.

It is worth mentioning here that Theorem 3 is a further step, small as it may be, towards characterizing the nerve of finite families K = {K_{1}, …, K_{n}} of convex compact sets in R^{d}. The nerve of K is defined as the simplicial complex with vertex set K, and some of the K_{i} form a simplex if their intersection is nonempty. The characterization is known only for d = 1, that is, for intervals [LB]. Helly’s theorem implies that the nerve is determined by its at most d–dimensional simplices. Theorem 3 gives a necessary condition the nerve of a family should always satisfy.

5. Tverberg’s theorem

One of the most beautiful theorems in combinatorial convexity is due to Tverberg [T1]. It is the r–partite version of Radon’s theorem, the bound (r − 1)(d + 1) + 1 appearing in it is best possible. For further information on Tverberg’s theorem the reader is advised to consult the excellent survey paper of Eckhoff [E].

Theorem 4. If X ⊂ R^{d} contains (r−1)(d+1)+1 elements, then there is a partition X = ∪_{1}^{r}X_{j} such that ∩_{1}^{r} conv X_{j} is nonempty.

The original proof [T1] is rather involved and difficult: later Tverberg gave two simpler proofs ([T2], [TV]). It came as a surprise, then, that Sarkaria [S] discovered how the colourful Carathéodory theorem implies Tverberg’s theorem. The proof which we describe below is a simplified variant of Sarkaria’s argument.

Proof. Writing n = (d + 1)(r − 1) we may assume X = {x_{0}, x_{1}, …, x_{n}}. So x_{i} is a d–dimensional vector; let y_{i} be the (d + 1)–dimensional vector whose first d components coincide with those of x_{i} and whose last component is 1.

We need an artificial tool now: choose vectors v_{1}, …, v_{r} ∈ R^{r−1} with the restriction that the only linear dependence (apart from a scalar multiplier) is

(4.1)  v_{1} + ⋯ + v_{r} = 0.

Consider now the (r − 1) × (d + 1) matrix v_{j}y_{i}^{T}, which is the product of the column vector v_{j} with the row vector y_{i}^{T}. Define A_{i} = {v_{1}y_{i}^{T} , v_{2}y_{i}^{T} , … v_{r}y_{i}^{T} } for every i = 0, 1, …, n, thus A_{i} is a set of vectors (or matrices, if you will) in R^{n}. Observe that 0 ∈ conv A_{i} for every i. This follows form (4.1) immediately. The conditions of the colourful Carathéodory theorem are satisfied for the n + 1 sets A_{i} ⊂ R^{n}. So there is a colourful set {a_{0}, …, a_{n}} containing 0 in its convex hull: ∑_{0}^{n} α_{i}a_{i} = 0 for some convex combination (i.e. α_{i} ≥ 0 and ∑ α_{i} = 1).

Now a_{i} = v_{k(i)}y_{i}^{T} with some k(i) ∈ {1, …, r}. Define I_{j} = {i : k(i) = j}. The sets I_{1}, …, I_{r} partition {0, 1, …, n}. Consequently, the sets X_{j} = {x_{i} : I ∈ I_{j}} partition X. We claim that this is a Tverberg partition, i.e., ∩_{1}^{r} conv X_{j} is not empty.

The proof is staightforward. Define z_{j} = ∑_{i∈I_{j}} α_{i}y_{i} for j ∈ {1, …, r}. We get from the equation ∑_{0}^{n} α_{i}a_{i} = 0

(4.2)  0 = ∑_{i=0}^{n} α_{i}v_{k(i)}y_{i}^{T} = ∑_{j=1}^{r} v_{j} ∑_{i∈I_{j}} α_{i}y_{i}^{T} = ∑_{1}^{r} v_{j}z_{j}^{T} .

Notice now that (4.1) trivially implies the existence of u ∈ R^{r−1} such that u^{T} v_{1} = 1, u^{T} v_{2} = −1, and u^{T} v_{j} = 0 for j ≠ 1, 2. Multiplying (4.2) with u^{T} from the left we get z_{1} = z_{2}. The same argument shows that

z := z_{1} = z_{2} = ⋯ = z_{r}.

Checking the last components here gives ∑_{i∈I_{j}} α_{i} = 1/r for every j. Write ẑ for the vector consisting of the first d components of z. Then rẑ is a point in conv X_{j} for every j = 1, …, r since rẑ = rẑ_{j} = ∑_{i∈I_{j}} rα_{i}x_{i} is a convex combination of elements of X_{j}, proving the claim.

The proof shows also that a positive solution of the main question in section 2 would give a polynomial time algorithm to find a Tverberg partition. At present such an algorithm is not known. This makes Problem 1 even more interesting.

Tverberg’s theorem has a colourful version, too. Given sets (colours) C_{1}, …, C_{d+1} in R^{d}, each of cardinality t, one wants to find ”many” pairwise disjoint colourful sets S_{1}, …, S_{r} such that ∩_{1}^{r} conv S_{j} is nonempty. The question is how large t = T (r, d) must be to ensure the existence of such sets S_{1}, …, S_{r}. Using algebraic topology Živaljević and Vrećica (see also [BLŽV], [Z], [M]) showed that T (r, d) ≤ 2p(r) − 1 where p(r) is the smallest prime that is at least r. Since p(r) < 2r always, T (r, d) ≤ 4r − 3. This settles the problem of finiteness of T (r, d), and does so with a good upper bound. The following question from [BL], however, remains open.

Conjecture 1. T(r,d)=r for every pair of positive integers r and d.

It is reassuring to know that the conjecture holds for some values of r and d: it is known (see [BL] for details) that T (2, d) = 2 and T (r, 2) = r, the cases d = 1 or r = 1 are completely trivial.

Finally, we mention the integer analogue of Tverberg’s problem: here one seeks the smallest number t(r, d) such that any set of more than t(r, d) points in Z^{d} has an integer Tverberg partition, namely a partition X = ⋃_{j=1}^{r} X_{j} such that ⋂_{j=1}^{r} conv(X_{j}) contains an integer point. The numbers t(r, d) are known to be finite, but their exact determination is an outstanding open problem, even for r = 2. Refer to [O] for the bounds 2^{d} < t(2, d) < d2^{d} and for related results.

6. How many simplices contain a point?

Assume now that X ⊂ R^{d} is ”large” in the sense that |X| = n is large. Carathéodory’s theorem says that if a is in the convex hull of X, then a belongs to a simplex of X. How many simplices contain a? Some points are contained in ”many” simplices of X. How many is this ”many”? Certainly not more than \binom{n}{d+1} (the total number of simplices) but the following result shows that some point is contained in a positive fraction of all simplices of X.

Theorem 5. There is a point a ∈ R^{d} that is contained in c_{d}\binom{n}{d+1} simplices of X, where c_{d} > 0 depends only on d.

The proof below gives c_{d} = (d + 1)^{−(d+1)}, in [B] Theorem 5 is proved with c_{d} = (d + 1)^{−d}. It is also shown there c_{d} cannot be larger than 2^{−d}. The best possible value of c_{d} is known only in the plane: Boros and Füredi [BF] proved that 2/9 is the largest possible value of c_{2}.

Proof of Theorem 5. By Tverberg’s theorem there is a partition X = ∪_{1}^{r}X_{i} with ∩_{1}^{r} conv X_{i} ≠ ∅, where

r = ⌊\frac{n − 1}{d + 1}⌋ + 1 ≥ \frac{n}{d + 1}.

We show that any point a ∈ ∩ conv X_{i} is contained in many simplices of X. Choose (d + 1) of the X_{i}, X_{i_{1}}, …, X_{i_{d+1}}, possibly with repetitions. By the colourful Carathéodory theorem, there is a choice x_{i_{1}} ∈ X_{i_{1}}, …, x_{i_{d+1}} ∈ X_{i_{d+1}} with a ∈ conv{x_{i_{1}}, …, x_{i_{d+1}}}. This is a simplex of X containing a. These simplices are distinct for distinct systems X_{i_{1}}, …, X_{i_{d+1}}. Thus a is contained in at least

\binom{r + d}{d + 1} ≥ (d + 1)^{−(d+1)}\binom{n}{d + 1}

simplices of X.

There is another proof of the above ”positive fraction” theorem, due to N. Alon [A]. Let F be the family of all simplices of X. By a theorem of Katchalski and Liu[KL] (see also Kalai [K] and Alon–Kalai [AKa]), a positive fraction of the members of F has a nonempty intersection if and only if a positive fraction of the (d + 1)–tuples from F have nonempty intersection. The reader will have no difficulty showing that the latter condition is implied by Tverberg’s theorem. However, the constant c_{d} coming from this proof is smaller than the above one.

The positive fraction theorem has a colourful version, too. Given sets (colours) C_{1}, …, C_{d+1} in R^{d}, each of size t, there is a point a ∈ R^{d} that is contained in c′_{d}t^{d+1} colourful simplices (where c′_{d} is a positive constant depending only on d). This is a particular case of the so called point selection theorem (Theorem 2.1 from [ABFK]). However, the following possible strengthening is open for d > 2.

Conjecture 2. Given sets (colours) C_{1}, …, C_{d+1} in R^{d}, each of size t, there is a point a ∈ R^{d} and subsets D_{i} ⊂ C_{i}, each of size at least b_{d}t such that a ∈ conv{x_{1}, … x_{d+1}} for every choice x_{1} ∈ D_{1}, … x_{d+1} ∈ D_{d+1}. Here the positive constant b_{d} depends only on d.

The conjecture is true in the planar case with constant b_{2} = 1/12 (see Lemma 8.1 in [BFL]), however, the best value of b_{2} is not known. Even more intriguing is the fact that the conjecture is open in the uncoloured case, i.e., when C_{1} = C_{2} = ⋯ = C_{d+1}.

7. Weak ε–nets

Given a set X ⊂ R^{d} of n elements and ε > 0, a set S ⊂ R^{d} is a weak ε–net for X, if S ∩ conv Y ≠ ∅ for every Y ⊂ X of at least εn elements. That is, the weak ε–net has to meet the convex hull of every ε–fraction of points of X. The question is, or rather was, whether there exists a weak ε–net S for X of size depending only on ε and d. The following theorem, due to Alon and Kleitman [AKl], turned out to be the crucial in the solution of the Hadwiger–Debrunner (p, q)–problem.

Theorem 6. Given a finite set X ⊂ R^{d} and ε > 0, there exits a weak ε–net S of size at most (d + 1)^{−(d+1)}ε^{−(d+1)}.

The proof is based on Theorem 5 and not directly on the colourful Carathéodory. It is an exciting open question what the best exponent of ε is in the theorem. It is clearly at least −1, and even in the plane, it may be just −1. This is an old open problem of Danzer (see [BC]). The exponent −(d + 1) has been since improved to essentially −d, and even to −1 in some cases when d = 2 (see [ABFK], [CEGGSW]), but the general question remains wide open.

Proof. An algorithm will show the existence of a small weak ε–net. Start with S := ∅.

Assume that at a certain step of the algorithm we have a set S. If there is no set Y ⊂ X of size εn with S ∩ conv Y = ∅, then S is a weak ε–net and we stop. In the opposite case, according to Theorem 5, there is a point a common to (d + 1)^{−(d+1)}\binom{εn}{d+1} simplices of X. Define S := S ∪ a.

In each step of the algorithm, the size of S increases by 1, and the number of simplices not met by S decreases by (d + 1)^{−(d+1)}\binom{εn}{d+1}. Since the number of simplices of X is \binom{n}{d+1}, the algorithm finishes after at most

\frac{\binom{n}{d+1}}{(d + 1)^{−(d+1)}\binom{εn}{d+1}}

steps proving the theorem.

References

[A] N. Alon, personal communication, 1995.

[ABFK] N. Alon, I. Bárány, Z. Füredi, D. Kleitman, Point selections and weak ε–nets for convex

hulls, Combinatorics, Prob., Comp., 1 (1992), 189–200.

CARATHÉODORY’S THEOREM, COLOURFUL AND APPLICABLE 9

[AKa] N. Alon, G. Kalai, A simple proof of the upper bound theorem, European J. Comb., 6 (1985), 211–214.

[AKl] N. Alon, D. Kleitman, Piercing convex sets and the Hadwiger–Debrunner (p, q)–problem,

Adv. Math., 96 (1992), 103–112.

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

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

[BL] I. Bárány, D.G. Larman, A coloured version of Tverberg’s theorem, J. London Math¿ Soc., 45 (1992), 314–320.

[BO] I. Bárány, S. Onn, Colourful linear programming, manuscript in preparation, 1995.

[BC] J. Beck, W. Chen, Irregularities of distributions, Cambridge Tracts in Math., 89 (1987),

Cambridge Univ. Press. [BLŽV] A. Björner, L. Lovász, R. Živaljević, S. Vrećica, Chessboard complexes and matching

complexes, J. London Math. Soc., 49 (1994), 25–40.

[BF] E. Boros, Z. Füredi, The number of triangles covering the center of an n–set, Geom. Dedi-

cata, 17 (1984), 69–77.

[CEGGSW] B. Chazelle, H. Edeldsbrunner, M. Grigni, L. Guibas, M. Sharir, E. Welzl Weak

ε–nets for convex sets, Discrete Comp. Geom., 13 (1995), 1–17.

[DGK] L. Danzer, B. Grünbaum, V. Klee, Helly’s theorem and its relatives, in Proc. Symposia in

Pure math. Vol VII, (V. Klee, ed), Providence, RI 1963.

[E] J. Eckhoff, Helly, Radon, and Carathéodory type theorems, in: Handbook of Convex Geom-

etry, (ed.: P.M. Gruber, J. Wills), North Holland,(1993), 389–448.

[JPY] D.S. Johnson, C.H. Papadimitriou, M. Yannakakis, How easy is local search?, J. Comp.

Sys. Sci., 37 (1988), 79–100.

[K] G. Kalai, Intersection patterns of convex sets, Israel J. Math., 48 (1984), 161–174.

[KL] . M. Katchalski, A. Liu, A problem of geometry in R^{d}, Proc. AMS, 75 (1979), 284–288.

[LB] C.G. Lekkerkerker, J.C. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math., 51 (1962), 45–64.

[Kv] Problem M 1157, Kvant 1989, no. 4, page 24 (in Russian).

[M] J. Matoušek, Note on the coloured Tverberg problem, J. Comb. Theory (B), to appear.

[MI] Problem, Mathematical Intelligencer, 14 no. 4 (1992), page 24.

[L] L. Lovász, personal communication, 1977

[ML] Problem 206. Matematikai Lapok, 25 (1974), page 181.

[O] S. Onn, On the geometry and computational complexity of Radon partitions in the integer lattice, SIAM J. Discr. Math., 4 (1991), 436–447.

10 CARATHÉODORY’S THEOREM, COLOURFUL AND APPLICABLE

[PY] C.H. Papadimitriou, M. Yannakakis, Optimization, approximation, and complexity classes,

J. Comp. Sys. Sci., 43 (1991), 425–440.

[S] K.S. Sarkaria, Tverberg’s theorem via number fields, Israel J. Math., 79 (1992), 317–320.

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

[T2] H. Tverberg, A generalization of Radon’s theorem II, Bull. Ausrtal. Math. Soc., 24 (1981), 321–325.

[TV] H. Tverberg, S. Vrećica, On a generalization of Radon’s theorem and the ham–sandwich theorem, European J. Comb., 24 (1993), 259–264.

[W] G. Wegner, D–collapsing and nerves of families of convex sets, Arch. Math., 26 (1975), 317–321.

[Z] G.M. Ziegler, Shellability of chessboard complexes, Israel J. Math., 87 (1994), 97–110. [ŽV] R. Živaljević, S. Vrećica, The coloured Tverberg ’s problem and complexes of injective

functions, J. Comb. Theory (A), 61 (1992), 309–318.