请输入您要查询的百科知识：

　

词条 Helly's theorem
释义

  1. Statement

  2. Proof

  3. See also

  4. Notes

  5. References

Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913,[1] but not published by him until 1923, by which time alternative proofs by {{harvtxt|Radon|1921}} and {{harvtxt|König|1922}} had already appeared. Helly's theorem gave rise to the notion of a Helly family.

Statement

Let {{math|X1, ..., Xn}} be a finite collection of convex subsets of {{math|Rd}}, with {{math|n > d}}. If the intersection of every {{math|d + 1}} of these sets is nonempty, then the whole collection has a nonempty intersection; that is,

For infinite collections one has to assume compactness:

Let {{math|{Xα} }} be a collection of compact convex subsets of {{math|Rd}}, such that every subcollection of cardinality at most {{math|d + 1}} has nonempty intersection. Then the whole collection has nonempty intersection.

Proof

We prove the finite version, using Radon's theorem as in the proof by {{harvtxt|Radon|1921}}. The infinite version then follows by the finite intersection property characterization of compactness: a collection of closed subsets of a compact space has a non-empty intersection if and only if every finite subcollection has a non-empty intersection (once you fix a single set, the intersection of all others with it are closed subsets of a fixed compact space).

The proof is by induction:

Base case: Let {{math|n {{=}} d + 2}}. By our assumptions, for every {{math|j {{=}} 1, ..., n}} there is a point {{math|xj}} that is in the common intersection of all {{math|Xi}} with the possible exception of {{math|Xj}}. Now we apply Radon's theorem to the set {{math|A {{=}} {x1, ..., xn},}} which furnishes us with disjoint subsets {{math|A1, A2}} of {{mvar|A}} such that the convex hull of {{math|A1}} intersects the convex hull of {{math|A2}}. Suppose that {{mvar|p}} is a point in the intersection of these two convex hulls. We claim that

Indeed, consider any {{math|j ∈ {1, ..., n}.}} We shall prove that {{math|p ∈ Xj.}} Note that the only element of {{mvar|A}} that may not be in {{math|Xj}} is {{math|xj}}. If {{math|xj ∈ A1}}, then {{math|xj ∉ A2}}, and therefore {{math|Xj ⊃ A2}}. Since {{math|Xj}} is convex, it then also contains the convex hull of {{math|A2}} and therefore also {{math|p ∈ Xj}}. Likewise, if {{math|xj ∉ A1}}, then {{math|Xj ⊃ A1}}, and by the same reasoning {{math|p ∈ Xj}}. Since {{mvar|p}} is in every {{math|Xj}}, it must also be in the intersection.

Above, we have assumed that the points {{math|x1, ..., xn}} are all distinct. If this is not the case, say {{math|xi {{=}} xk}} for some {{math|i ≠ k}}, then {{math|xi}} is in every one of the sets {{math|Xj}}, and again we conclude that the intersection is nonempty. This completes the proof in the case {{math|n {{=}} d + 2}}.

Inductive Step: Suppose {{math|n > d + 2}} and that the statement is true for {{math|n−1}}. The argument above shows that any subcollection of {{math|d + 2}} sets will have nonempty intersection. We may then consider the collection where we replace the two sets {{math|Xn−1}} and {{math|Xn}} with the single set {{math|Xn−1 ∩ Xn}}. In this new collection, every subcollection of {{math|d + 1}} sets will have nonempty intersection. The inductive hypothesis therefore applies, and shows that this new collection has nonempty intersection. This implies the same for the original collection, and completes the proof.

See also

  • Carathéodory's theorem
  • Shapley–Folkman lemma
  • Krein–Milman theorem
  • Choquet theory
  • Radon's theorem, and its generalization, Tverberg's theorem

Notes

1. ^{{harvtxt|Danzer|Grünbaum|Klee|1963}}.

References

  • {{citation

| last = Bollobás | first = B. | author-link = Béla Bollobás
| contribution = Problem 29, Intersecting Convex Sets: Helly's Theorem
| isbn = 0-521-69395-0
| pages = 90–91
| publisher = Cambridge University Press
| title = The Art of Mathematics: Coffee Time in Memphis
| year = 2006}}.
  • {{citation

| last1 = Danzer | first1 = L.
| last2 = Grünbaum | first2 = B. | author2-link = Branko Grünbaum
| last3 = Klee | first3 = V. | author3-link = Victor Klee
| contribution = Helly's theorem and its relatives
| pages = 101–180
| publisher = American Mathematical Society
| series = Proc. Symp. Pure Math.
| title = Convexity
| url =
| volume = 7
| year = 1963}}.
  • {{citation

| last = Eckhoff | first = J.
| contribution = Helly, Radon, and Carathéodory type theorems
| location = Amsterdam
| pages = 389–448
| publisher = North-Holland
| title = Handbook of Convex Geometry
| volume = A, B
| year = 1993}}.
  • Heinrich Guggenheimer (1977) Applicable Geometry, page 137, Krieger, Huntington {{ISBN|0-88275-368-1}} .
  • {{citation

| last = Helly | first = E. | author-link = Eduard Helly
| journal = Jahresbericht der Deutschen Mathematiker-Vereinigung
| pages = 175–176
| title = Über Mengen konvexer Körper mit gemeinschaftlichen Punkten
| volume = 32
| year = 1923}}.
  • {{citation

| last = König | first = D. | author-link = Dénes Kőnig
| doi = 10.1007/BF01215899
| issue = 1
| journal = Mathematische Zeitschrift
| pages = 208–220
| title = Über konvexe Körper
| volume = 14
| year = 1922}}.
  • {{citation

| last = Radon | first = J. | author-link = Johann Radon
| doi = 10.1007/BF01464231
| issue = 1–2
| journal = Mathematische Annalen
| pages = 113–115
| title = Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten
| volume = 83
| year = 1921}}.

4 : Theorems in convex geometry|Theorems in discrete geometry|Articles containing proofs|Geometric transversal theory
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/9/28 3:20:17