![Helly's theorem](https://upload.wikimedia.org/wikipedia/commons/6/65/Helly%27s_theorem.svg)
Helly's theorem is a basic result in
discrete geometry
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geome ...
on the
intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...
of
convex set
In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex r ...
s. It was discovered by
Eduard Helly
Eduard Helly (June 1, 1884 in Vienna – 28 November 1943 in Chicago) was a mathematician after whom Helly's theorem, Helly families, Helly's selection theorem, Helly metric, and the Helly–Bray theorem were named.
Life
Helly earned his doct ...
in 1913,
[.] but not published by him until 1923, by which time alternative proofs by and had already appeared. Helly's theorem gave rise to the notion of a
Helly family
In combinatorics, a Helly family of order is a family of sets in which every minimal ''subfamily with an empty intersection'' has or fewer sets in it. Equivalently, every finite subfamily such that every -fold intersection is non-empty has non ...
.
Statement
Let be a finite collection of convex subsets of , with . If the intersection of every of these sets is nonempty, then the whole collection has a nonempty intersection; that is,
:
For infinite collections one has to assume compactness:
Let be a collection of
compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in British ...
convex subsets of , such that every subcollection of
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
at most has nonempty intersection. Then the whole collection has nonempty intersection.
Proof
We prove the finite version, using
Radon's theorem
In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that any set of ''d'' + 2 points in R''d'' can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these conve ...
as in the proof by . The infinite version then follows by the
finite intersection property In general topology, a branch of mathematics, a non-empty family ''A'' of subsets of a set X is said to have the finite intersection property (FIP) if the intersection over any finite subcollection of A is non-empty. It has the strong finite inters ...
characterization of
compactness
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...
: 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
Induction, Inducible or Inductive may refer to:
Biology and medicine
* Labor induction (birth/pregnancy)
* Induction chemotherapy, in medicine
* Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
:
Base case: Let . By our assumptions, for every there is a point that is in the common intersection of all with the possible exception of . Now we apply
Radon's theorem
In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that any set of ''d'' + 2 points in R''d'' can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these conve ...
to the set which furnishes us with disjoint subsets of such that the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
of intersects the convex hull of . Suppose that is a point in the intersection of these two convex hulls. We claim that
:
Indeed, consider any We shall prove that Note that the only element of that may not be in is . If , then , and therefore . Since is convex, it then also contains the convex hull of and therefore also . Likewise, if , then , and by the same reasoning . Since is in every , it must also be in the intersection.
Above, we have assumed that the points are all distinct. If this is not the case, say for some , then is in every one of the sets , and again we conclude that the intersection is nonempty. This completes the proof in the case .
Inductive Step: Suppose and that the statement is true for . The argument above shows that any subcollection of sets will have nonempty intersection. We may then consider the collection where we replace the two sets and with the single set . In this new collection, every subcollection of 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.
Colorful 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 .
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.
Fractional Helly theorem
For every ''a'' > 0 there is some ''b'' > 0 such that, if are ''n'' convex subsets of , 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
*
Kirchberger's theorem Kirchberger's theorem is a theorem in discrete geometry, on linear separability. The two-dimensional version of the theorem states that, if a finite set of red and blue points in the Euclidean plane has the property that, for every four points, the ...
*
Shapley–Folkman lemma
The Shapley–Folkman lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ros ...
*
Krein–Milman theorem
In the mathematical theory of functional analysis, the Krein–Milman theorem is a proposition about compact convex sets in locally convex topological vector spaces (TVSs).
This theorem generalizes to infinite-dimensional spaces and to arbitrar ...
*
Choquet theory In mathematics, Choquet theory, named after Gustave Choquet, is an area of functional analysis and convex analysis concerned with measures which have support on the extreme points of a convex set ''C''. Roughly speaking, every vector of ''C'' sho ...
*
Radon's theorem
In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that any set of ''d'' + 2 points in R''d'' can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these conve ...
, and its generalization,
Tverberg's theorem
In discrete geometry, Tverberg's theorem, first stated by , is the result that sufficiently many points in ''d''-dimensional Euclidean space can be partitioned into subsets with intersecting convex hulls. Specifically, for any set of
:(d + 1)(r ...
Notes
References
*.
*.
*.
*
Heinrich Guggenheimer
Heinrich Walter Guggenheimer (July 21, 1924 – March 4, 2021) was a German-born Swiss-American mathematician who has contributed to knowledge in differential geometry, topology, algebraic geometry, and convexity. He has also contributed volume ...
(1977) ''Applicable Geometry'', page 137, Krieger, Huntington .
*.
*.
*{{citation
, last = Radon , first = J. , author-link = Johann Radon
, doi = 10.1007/BF01464231
, issue = 1–2
, journal =
Mathematische Annalen
''Mathematische Annalen'' (abbreviated as ''Math. Ann.'' or, formerly, ''Math. Annal.'') is a German mathematical research journal founded in 1868 by Alfred Clebsch and Carl Neumann. Subsequent managing editors were Felix Klein, David Hilbert, ...
, pages = 113–115
, title = Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten
, volume = 83
, year = 1921, s2cid = 121627696 .
Theorems in convex geometry
Theorems in discrete geometry
Articles containing proofs
Geometric transversal theory