Authors: Živaljević, Rade 
Vrećica, Siniša
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: The colored Tverberg's problem and complexes of injective functions
Journal: Journal of Combinatorial Theory, Series A
Volume: 61
Issue: 2
First page: 309
Last page: 318
Issue Date: 1-Jan-1992
Rank: M21
ISSN: 0097-3165
DOI: 10.1016/0097-3165(92)90028-S
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.
Publisher: Elsevier

Show full item record


checked on Jun 14, 2024

Page view(s)

checked on May 10, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.