Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

Piercing convex sets


Authors: Noga Alon and Daniel J. Kleitman
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
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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.
  • [2] N. Alon and G. Kalai, A simple proof of the upper bound theorem, European J. Combinatorics 6 (1985), 211-214. MR 818593 (87i:52008)
  • [3] N. Alon and D. J. Kleitman, Piercing convex sets and the Hadwiger Debrunner $ (p,q)$ problem, Adv. Math. (to appear). MR 1149871 (93a:52005)
  • [4] I. Bárány, A generalization of Caratheodory's theorem, Discrete Math. 40 (1982), 141-152. MR 676720 (84c:52014)
  • [5] 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.
  • [6] V. L. Dol'nikov, A coloring problem, Sibirsk. Mat. Zh. 13 (1972), 1272-1283; English transl. in Siberian Math. J. 13 (1972), 886-894. MR 0329949 (48:8288)
  • [7] J. Eckhoff, An upper bound theorem for families of convex sets, Geom. Dedicata 19 (1985), 217-227. MR 809468 (87b:52008)
  • [8] -, Helly, Radon, and Carathèodory type theorems, Handbook of Convex Geometry (to appear).
  • [9] B. E. Fullbright, Intersectional properties of certain families of compact convex sets, Pacific J. Math. 50 (1974), 57-62. MR 0338926 (49:3689)
  • [10] B. Grünbaum, On intersections of similar sets, Portugal Math. 18 (1959), 155-164. MR 0125491 (23:A2792)
  • [11] -, Lectures on combinatorial geometry, Mimeographed Notes, Univ. of Washington, Seattle, 1974.
  • [12] H. Hadwiger and H. Debrunner, Über eine Variante zum Helly'schen Satz, Arch. Math. 8 (1957), 309-313. MR 0092987 (19:1192a)
  • [13] H. Hadwiger, H. Debrunner, and V. Klee, Combinatorial geometry in the plane, Holt, Rinehart, and Winston, New York, 1964. MR 0164279 (29:1577)
  • [14] E. Helly, Über Mengen konvexer Körper mit gemeinschaftlichen Punkten, Jahresber. Deutsch. Math. Verein. 32 (1923), 175-176.
  • [15] M. Katchalski and A. Liu, A problem of geometry in $ {R^d}$, Proc. Amer. Math. Soc. 75 (1979), 284-288. MR 532152 (80h:52010)
  • [16] G. Kalai, Intersection patterns of convex sets, Israel J. Math. 48 (1984), 161-174. MR 770699 (86c:52002)
  • [17] A. Schrijver, Theory of linear and integer programming, Wiley, New York, 1986. MR 874114 (88m:90090)
  • [18] H. Tverberg, A generalization of Radon's Theorem, J. London Math. Soc. (2) 41 (1966), 123-128. MR 0187147 (32:4601)
  • [19] G. Wegner, Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner, Israel J. Math. 3 (1965), 187-198. MR 0203586 (34:3436)
  • [20] -, d-collapsing and nerves of families of convex sets, Arch. Math. 26 (1975), 317-321. MR 0375333 (51:11528)
  • [21] -, Über Helly-Gallaische Stichzahlprobleme, 3, Koll. Discrete Geom. Salzburg (1985), 277-282.

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 52A35

Retrieve articles in all journals with MSC (2000): 52A35


Additional Information

DOI: https://doi.org/10.1090/S0273-0979-1992-00304-X
Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society