Piercing convex sets
HTML articles powered by AMS MathViewer
- by Noga Alon and Daniel J. Kleitman PDF
- Bull. Amer. Math. Soc. 27 (1992), 252-256 Request permission
Abstract:
A family of sets has the $(p,q)$ property if among any p members of the family some q have a nonempty intersection. It is shown that for every $p \geq q \geq d + 1$ there is a $c = c(p,q,d) < \infty$ such that for every family $\mathcal {F}$ of compact, convex sets in ${R^d}$ that has the ($(p,q)$) property there is a set of at most c points in ${R^d}$ that intersects each member of $\mathcal {F}$. This extends Helly’s Theorem and settles an old problem of Hadwiger and Debrunner.References
-
N. Alon, I. Bárány, Z.. Füredi, and D. J. Kleitman, Point selections and weak $\varepsilon$-nets for convex hulls, Combin. Prob. and Computing 1, submitted.
- N. Alon and G. Kalai, A simple proof of the upper bound theorem, European J. Combin. 6 (1985), no. 3, 211–214. MR 818593, DOI 10.1016/S0195-6698(85)80029-9
- Noga Alon and Daniel J. Kleitman, Piercing convex sets, Bull. Amer. Math. Soc. (N.S.) 27 (1992), no. 2, 252–256. MR 1149871, DOI 10.1090/S0273-0979-1992-00304-X
- Imre Bárány, A generalization of Carathéodory’s theorem, Discrete Math. 40 (1982), no. 2-3, 141–152. MR 676720, DOI 10.1016/0012-365X(82)90115-7 L. Danzer, B. Grünbaum, and V. Klee, Helly’s theorem and its relatives, Proc. Sympos. Pure Math., vol. 7, Amer. Math. Soc., Providence, RI, 1963, pp. 101-180.
- V. L. Dol′nikov, A certain coloring problem, Sibirsk. Mat. Ž. 13 (1972), 1272–1283, 1420 (Russian). MR 0329949
- Jürgen Eckhoff, An upper-bound theorem for families of convex sets, Geom. Dedicata 19 (1985), no. 2, 217–227. MR 809468, DOI 10.1007/BF00181472 —, Helly, Radon, and Carathèodory type theorems, Handbook of Convex Geometry (to appear).
- B. E. Fullbright, Intersectional properties of certain families of compact convex sets, Pacific J. Math. 50 (1974), 57–62. MR 338926, DOI 10.2140/pjm.1974.50.57
- Branko Grünbaum, On intersections of similar sets, Portugal. Math. 18 (1959), 155–164. MR 125491 —, Lectures on combinatorial geometry, Mimeographed Notes, Univ. of Washington, Seattle, 1974.
- H. Hadwiger and H. Debrunner, Über eine Variante zum Hellyschen Satz, Arch. Math. (Basel) 8 (1957), 309–313 (German). MR 92987, DOI 10.1007/BF01898794
- Hugo Hadwiger and Hans Debrunner, Combinatorial geometry in the plane, Holt, Rinehart and Winston, New York, 1964. Translated by Victor Klee. With a new chapter and other additional material supplied by the translator. MR 0164279 E. Helly, Über Mengen konvexer Körper mit gemeinschaftlichen Punkten, Jahresber. Deutsch. Math. Verein. 32 (1923), 175-176.
- M. Katchalski and A. Liu, A problem of geometry in $\textbf {R}^{n}$, Proc. Amer. Math. Soc. 75 (1979), no. 2, 284–288. MR 532152, DOI 10.1090/S0002-9939-1979-0532152-6
- Gil Kalai, Intersection patterns of convex sets, Israel J. Math. 48 (1984), no. 2-3, 161–174. MR 770699, DOI 10.1007/BF02761162
- Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
- H. Tverberg, A generalization of Radon’s theorem, J. London Math. Soc. 41 (1966), 123–128. MR 187147, DOI 10.1112/jlms/s1-41.1.123
- G. Wegner, Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner, Israel J. Math. 3 (1965), 187–198 (German, with English summary). MR 203586, DOI 10.1007/BF03008396
- Gerd Wegner, $d$-collapsing and nerves of families of convex sets, Arch. Math. (Basel) 26 (1975), 317–321. MR 375333, DOI 10.1007/BF01229745 —, Über Helly-Gallaische Stichzahlprobleme, 3, Koll. Discrete Geom. Salzburg (1985), 277-282.
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 27 (1992), 252-256
- MSC (2000): Primary 52A35
- DOI: https://doi.org/10.1090/S0273-0979-1992-00304-X
- MathSciNet review: 1149871