Английская Википедия:Helly's theorem

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Helly's theorem.svg

Helly's theorem for the Euclidean plane: if a family of convex sets has a nonempty intersection for every triple of sets, then the whole family has a nonempty intersection.

Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913, but not published by him until 1923, by which time alternative proofs by Шаблон:Harvtxt and Шаблон:Harvtxt had already appeared. Helly's theorem gave rise to the notion of a Helly family.

Statement

Let Шаблон:Math be a finite collection of convex subsets of Шаблон:Math, with Шаблон:Math. If the intersection of every Шаблон:Math of these sets is nonempty, then the whole collection has a nonempty intersection; that is,

<math>\bigcap_{j=1}^n X_j\ne\varnothing.</math>

For infinite collections one has to assume compactness:

Let Шаблон:Math be a collection of compact convex subsets of Шаблон:Math, such that every subcollection of cardinality at most Шаблон:Math 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. 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. By our assumptions, for every Шаблон:Math there is a point Шаблон:Math that is in the common intersection of all Шаблон:Math with the possible exception of Шаблон:Math. Now we apply Radon's theorem to the set Шаблон:Math which furnishes us with disjoint subsets Шаблон:Math of Шаблон:Mvar such that the convex hull of Шаблон:Math intersects the convex hull of Шаблон:Math. Suppose that Шаблон:Mvar is a point in the intersection of these two convex hulls. We claim that

<math>p\in\bigcap_{j=1}^n X_j.</math>

Indeed, consider any Шаблон:Math We shall prove that Шаблон:Math Note that the only element of Шаблон:Mvar that may not be in Шаблон:Math is Шаблон:Math. If Шаблон:Math, then Шаблон:Math, and therefore Шаблон:Math. Since Шаблон:Math is convex, it then also contains the convex hull of Шаблон:Math and therefore also Шаблон:Math. Likewise, if Шаблон:Math, then Шаблон:Math, and by the same reasoning Шаблон:Math. Since Шаблон:Mvar is in every Шаблон:Math, it must also be in the intersection.

Above, we have assumed that the points Шаблон:Math are all distinct. If this is not the case, say Шаблон:Math for some Шаблон:Math, then Шаблон:Math is in every one of the sets Шаблон:Math, and again we conclude that the intersection is nonempty. This completes the proof in the case Шаблон:Math.

Inductive Step: Suppose Шаблон:Math and that the statement is true for Шаблон:Math. The argument above shows that any subcollection of Шаблон:Math sets will have nonempty intersection. We may then consider the collection where we replace the two sets Шаблон:Math and Шаблон:Math with the single set Шаблон:Math. In this new collection, every subcollection of Шаблон:Math 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.

Шаблон:AnchorColorful Helly theorem

The colorful Helly theorem is an extension of Helly's theorem in which, instead of one collection, there are d+1 collections of convex subsets of Шаблон:Math.

If, for every choice of a transversal – one set from every collection – there is a point in common to all the chosen sets, then for at least one of the collections, there is a point in common to all sets in the collection.

Figuratively, one can consider the d+1 collections to be of d+1 different colors. Then the theorem says that, if every choice of one-set-per-color has a non-empty intersection, then there exists a color such that all sets of that color have a non-empty intersection.

Шаблон:AnchorFractional Helly theorem

For every a > 0 there is some b > 0 such that, if Шаблон:Math are n convex subsets of Шаблон:Math, and at least an a-fraction of (d+1)-tuples of the sets have a point in common, then a fraction of at least b of the sets have a point in common.

See also

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

References

• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Heinrich Guggenheimer (1977) Applicable Geometry, page 137, Krieger, Huntington Шаблон:ISBN .
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.