A geometric proof of the colored Tverberg theorem

J. Matoušek, M. Tancer, U. Wagner, Discrete & Computational Geometry 47 (2012) 245–265.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
Abstract
The colored Tverberg theorem asserts that for eve;ry d and r there exists t=t(d,r) such that for every set C ⊂ ℝ d of cardinality (d + 1)t, partitioned into t-point subsets C 1, C 2,...,C d+1 (which we think of as color classes; e. g., the points of C 1 are red, the points of C 2 blue, etc.), there exist r disjoint sets R 1, R 2,...,R r⊆C that are rainbow, meaning that {pipe}R i∩C j{pipe}≤1 for every i,j, and whose convex hulls all have a common point. All known proofs of this theorem are topological. We present a geometric version of a recent beautiful proof by Blagojević, Matschke, and Ziegler, avoiding a direct use of topological methods. The purpose of this de-topologization is to make the proof more concrete and intuitive, and accessible to a wider audience.
Publishing Year
Date Published
2012-03-01
Journal Title
Discrete & Computational Geometry
Acknowledgement
We would like to thank Marek Krcál for useful discussions at initial stages of this research. We also thank Günter M. Ziegler for valuable comments, and Peter Landweber and two anonymous referees for detailed comments and corrections that greatly helped to improve the presentation. In particular, we are indebted to one of the referees for pointing out to us reference [19]. M. Tancer is supported by the grants SVV-2010-261313 (Discrete Methods and Algorithms) and GAUK 49209. U. Wagner’s research is supported by the Swiss National Science Foundation (SNF Projects 200021- 125309 and 200020-125027).
Volume
47
Issue
2
Page
245 - 265
IST-REx-ID

Cite this

Matoušek J, Tancer M, Wagner U. A geometric proof of the colored Tverberg theorem. Discrete & Computational Geometry. 2012;47(2):245-265. doi:10.1007/s00454-011-9368-2
Matoušek, J., Tancer, M., & Wagner, U. (2012). A geometric proof of the colored Tverberg theorem. Discrete & Computational Geometry, 47(2), 245–265. https://doi.org/10.1007/s00454-011-9368-2
Matoušek, Jiří, Martin Tancer, and Uli Wagner. “A Geometric Proof of the Colored Tverberg Theorem.” Discrete & Computational Geometry 47, no. 2 (2012): 245–65. https://doi.org/10.1007/s00454-011-9368-2.
J. Matoušek, M. Tancer, and U. Wagner, “A geometric proof of the colored Tverberg theorem,” Discrete & Computational Geometry, vol. 47, no. 2, pp. 245–265, 2012.
Matoušek J, Tancer M, Wagner U. 2012. A geometric proof of the colored Tverberg theorem. Discrete & Computational Geometry. 47(2), 245–265.
Matoušek, Jiří, et al. “A Geometric Proof of the Colored Tverberg Theorem.” Discrete & Computational Geometry, vol. 47, no. 2, Springer, 2012, pp. 245–65, doi:10.1007/s00454-011-9368-2.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar