The colored Tverberg's problem and complexes of injective functions

Abstract

Let t, r, and d be positive integers and let C1, C2, ..., Cd+1 be a collection of (d + 1) disjoint sets in Rd, called colors, each of cardinality at least t. If S = {a1, a2, ..., ad+1} is a subset of A {colon equals} ∪i=1d+1 Ci, then both S and the, possibly degenerate, simplex conv S is called multicolored if S ∩ Ci ≠ {circled division slash} for all 1 ≤ i ≤ d + 1. Let T(r, d) denotes the smallest value t such that for every collection of "colors" {Ci | 1 ≤ i ≤ d + 1}, |Ci| ≥ t, there exist r disjoint, multicolored sets Si, i = 1, ..., r, such that ∩i=1r conv(Si) ≠ {circled division slash}. It is proved that T(r, d) ≤ 4r-1 for all r and T(r, d) ≤ 2r - 1 for all primes r. This estimate answers a question from (Bárány et al., in "Proceedings, 5th Annual Sympos. Comput. Geom., 1989," pp. 140-144) and at the same time provides a missing link of the proof that the number hd(n) of halving hyperplanes for a set of n points in Rd satisfies the inequality hd(n) ≤ O(nd-ε) for some ε > 0.