Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format
Bulletin of the American Mathematical Society
Bulletin of the American Mathematical Society
ISSN 1088-9485(e) ISSN 0273-0979(p)

     

Piercing convex sets

Author(s): Noga Alon; Daniel J. Kleitman
Journal: Bull. Amer. Math. Soc. 27 (1992), 252-256.
MSC (2000): Primary 52A35
MathSciNet review: 1149871
Retrieve article in: 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:

[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: 10.1090/S0273-0979-1992-00304-X
PII: S 0273-0979(1992)00304-X
Copyright of article: Copyright 1992, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia