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 |

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. |

Publisher: | Elsevier |

Show full item record

#### SCOPUS^{TM}

Citations

104
checked on Mar 20, 2023

#### Page view(s)

18
checked on Mar 21, 2023

#### Google Scholar^{TM}

Check
#### Altmetric

#### Altmetric

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