Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Helly's theorem
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{short description|Theorem about the intersections of d-dimensional convex sets}} {{distinguish|Helly's selection theorem}} [[File:Helly's theorem.svg|thumb|400px|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 (set theory)|intersection]] of [[convex set]]s. It was discovered by [[Eduard Helly]] in 1913,<ref>{{harvtxt|Danzer|Grünbaum|Klee|1963}}.</ref> 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|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} be a finite collection of convex subsets of <math>\R^d</math>, with <math>n\geq d+1</math>. If the intersection of every <math>d+1</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>\{X_\alpha\}</math> be a collection of [[compact set|compact]] convex subsets of <math>\R^d</math>, such that every subcollection of [[cardinality]] at most <math>d+1</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|Radon|1921}}. The infinite version then follows by the [[finite intersection property]] characterization of [[Compact space|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 [[mathematical induction|induction]]: '''Base case:''' Let {{math|''n'' {{=}} ''d'' + 2}}. By our assumptions, for every {{math|''j'' {{=}} 1, ..., ''n''}} there is a point {{math|''x<sub>j</sub>''}} that is in the common intersection of all {{math|''X<sub>i</sub>''}} with the possible exception of {{math|''X<sub>j</sub>''}}. Now we apply [[Radon's theorem]] to the set {{math|''A'' {{=}} {''x''<sub>1</sub>, ..., ''x<sub>n</sub>''},}} which furnishes us with disjoint subsets {{math|''A''<sub>1</sub>, ''A''<sub>2</sub>}} of {{mvar|A}} such that the [[convex hull]] of {{math|''A''<sub>1</sub>}} intersects the convex hull of {{math|''A''<sub>2</sub>}}. Suppose that {{mvar|p}} 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|''j'' ∈ {1, ..., ''n''}.}} We shall prove that {{math|''p'' ∈ ''X<sub>j</sub>''.}} Note that the only element of {{mvar|A}} that may not be in {{math|''X<sub>j</sub>''}} is {{math|''x<sub>j</sub>''}}. If {{math|''x<sub>j</sub>'' ∈ ''A''<sub>1</sub>}}, then {{math|''x<sub>j</sub>'' ∉ ''A''<sub>2</sub>}}, and therefore {{math|''X<sub>j</sub>'' ⊃ ''A''<sub>2</sub>}}. Since {{math|''X<sub>j</sub>''}} is convex, it then also contains the convex hull of {{math|''A''<sub>2</sub>}} and therefore also {{math|''p'' ∈ ''X<sub>j</sub>''}}. Likewise, if {{math|''x<sub>j</sub>'' ∉ ''A''<sub>1</sub>}}, then {{math|''X<sub>j</sub>'' ⊃ ''A''<sub>1</sub>}}, and by the same reasoning {{math|''p'' ∈ ''X<sub>j</sub>''}}. Since {{mvar|p}} is in every {{math|''X<sub>j</sub>''}}, it must also be in the intersection. Above, we have assumed that the points {{math|''x''<sub>1</sub>, ..., ''x<sub>n</sub>''}} are all distinct. If this is not the case, say {{math|''x<sub>i</sub>'' {{=}} ''x<sub>k</sub>''}} for some {{math|''i'' ≠ ''k''}}, then {{math|''x<sub>i</sub>''}} is in every one of the sets {{math|''X<sub>j</sub>''}}, 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|''X''<sub>''n''−1</sub>}} and {{math|''X<sub>n</sub>''}} with the single set {{math|''X''<sub>''n''−1</sub> ∩ ''X<sub>n</sub>''}}. 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. == {{Anchor|colorful}}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 {{math|'''R'''<sup>''d''</sup>}}. 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.<ref name=":0">{{citation|last=Kalai|first=Gil|date=2019-03-15|title=News on Fractional Helly, Colorful Helly, and Radon|url=https://gilkalai.wordpress.com/2019/03/15/news-on-fractional-helly-colorful-helly-and-radon/|access-date=2020-07-13|website=Combinatorics and more|language=en}}</ref> == {{Anchor|fractional}}Fractional Helly theorem == For every ''a'' > 0 there is some ''b'' > 0 such that, if {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} are ''n'' convex subsets of {{math|'''R'''<sup>''d''</sup>}}, 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.<ref name=":0" /> == See also == * [[Carathéodory's theorem (convex hull)|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]] * [[Cantor's intersection theorem]] - another theorem on intersection of sets * [[Helly Family]] ==Notes== {{reflist}} ==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| s2cid = 128041360 }}. *{{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| s2cid = 121627696 }}. [[Category:Theorems in convex geometry]] [[Category:Theorems in discrete geometry]] [[Category:Articles containing proofs]] [[Category:Geometric transversal theory]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Anchor
(
edit
)
Template:Citation
(
edit
)
Template:Distinguish
(
edit
)
Template:Harvtxt
(
edit
)
Template:ISBN
(
edit
)
Template:Math
(
edit
)
Template:Mvar
(
edit
)
Template:Reflist
(
edit
)
Template:Short description
(
edit
)