|
Piercing convex sets
Authors:
Noga Alon and Daniel J. Kleitman
Journal:
Bull. Amer. Math. Soc. 27 (1992), 252-256
MSC (2000):
Primary 52A35
MathSciNet review:
1149871
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: A family of sets has the property if among any p members of the family some q have a nonempty intersection. It is shown that for every there is a such that for every family of compact, convex sets in that has the ( ) property there is a set of at most c points in that intersects each member of . This extends Helly's Theorem and settles an old problem of Hadwiger and Debrunner.
- [1]
N. Alon, I. Bárány, Z.. Füredi, and D. J. Kleitman, Point selections and weak
-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.
Combin. 6 (1985), no. 3, 211–214. MR 818593
(87i:52008)
- [3]
Noga
Alon and Daniel
J. Kleitman, Piercing convex sets, Bull. Amer. Math. Soc. (N.S.) 27 (1992), no. 2, 252–256. MR 1149871
(93a:52005), http://dx.doi.org/10.1090/S0273-0979-1992-00304-X
- [4]
Imre
Bárány, A generalization of
Carathéodory’s theorem, Discrete Math.
40 (1982), no. 2-3, 141–152. MR 676720
(84c:52014), http://dx.doi.org/10.1016/0012-365X(82)90115-7
- [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 certain coloring problem, Sibirsk. Mat.
Ž. 13 (1972), 1272–1283, 1420 (Russian). MR 0329949
(48 #8288)
- [7]
Jürgen
Eckhoff, An upper-bound theorem for families of convex sets,
Geom. Dedicata 19 (1985), no. 2, 217–227. MR 809468
(87b:52008), http://dx.doi.org/10.1007/BF00181472
- [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]
Branko
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 Hellyschen Satz, Arch.
Math. (Basel) 8 (1957), 309–313 (German). MR 0092987
(19,1192a)
- [13]
Hugo
Hadwiger and Hans
Debrunner, Combinatorial geometry in the plane, Translated by
Victor Klee. With a new chapter and other additional material supplied by
the translator, 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
𝑅ⁿ, Proc. Amer. Math. Soc.
75 (1979), no. 2,
284–288. MR
532152 (80h:52010), http://dx.doi.org/10.1090/S0002-9939-1979-0532152-6
- [16]
Gil
Kalai, Intersection patterns of convex sets, Israel J. Math.
48 (1984), no. 2-3, 161–174. MR 770699
(86c:52002), http://dx.doi.org/10.1007/BF02761162
- [17]
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
(88m:90090)
- [18]
H.
Tverberg, A generalization of Radon’s theorem, J. London
Math. Soc. 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 (German, with English summary). MR 0203586
(34 #3436)
- [20]
Gerd
Wegner, 𝑑-collapsing and nerves of families of convex
sets, Arch. Math. (Basel) 26 (1975), 317–321.
MR
0375333 (51 #11528)
- [21]
-, Über Helly-Gallaische Stichzahlprobleme, 3, Koll. Discrete Geom. Salzburg (1985), 277-282.
- [1]
- N. Alon, I. Bárány, Z.. Füredi, and D. J. Kleitman, Point selections and weak
-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
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
, 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:
http://dx.doi.org/10.1090/S0273-0979-1992-00304-X
PII:
S 0273-0979(1992)00304-X
Article copyright:
© Copyright 1992 American Mathematical Society
|