Editing Carathéodory's theorem (convex hull)

{{short description|Point in the convex hull of a set P in Rd, is the convex combination of d+1 points in P}}
{{other uses|Carathéodory's theorem (disambiguation)}}
'''Carathéodory's theorem''' is a theorem in [[convex geometry]]. It states that if a point <math>x</math> lies in the [[convex hull]] <math>\mathrm{Conv}(P)</math> of a set <math>P\subset \R^d</math>, then <math>x</math> lies in some ''<math>d</math>''-dimensional [[simplex]] with vertices in <math>P</math>. Equivalently, <math>x</math> can be written as the [[convex combination]] of <math>d+1</math> or fewer points in <math>P</math>. Additionally, <math>x</math> can be written as the convex combination of at most <math>d+1</math> ''extremal'' points in <math>P</math>, as non-extremal points can be removed from <math>P</math> without changing the membership of ''<math>x</math>'' in the convex hull.

An equivalent theorem for [[Conical combination|conical combinations]] states that if a point <math>x</math> lies in the [[conical hull]] <math>\mathrm{Cone}(P)</math> of a set <math>P\subset \R^d</math>, then <math>x</math> can be written as the conical combination of at most <math>d</math> points in <math>P</math>.<ref name="lp">{{Cite Lovasz Plummer|mode=cs1}}</ref>{{rp|257}} 

Two other theorems of [[Helly's theorem|Helly]] and [[Radon's theorem|Radon]] are closely related to Carathéodory's theorem: the latter theorem can be used to prove the former theorems and vice versa.<ref>{{cite conference |last1=Danzer |first1=L. |last2=Grünbaum |first2=B. |author2-link=Branko Grünbaum |last3=Klee |first3=V. |author3-link=Victor Klee |year=1963 |title=Convexity |url= |series=Proc. Symp. Pure Math. |publisher=[[American Mathematical Society]] |volume=7 |pages=101–179 |contribution=Helly's theorem and its relatives}} See in particular p.109</ref>

The result is named for [[Constantin Carathéodory]], who proved the theorem in 1911 for the case when <math>P</math> is [[Compact space|compact]].<ref>{{Cite journal|last=Carathéodory|first=C.|title=Über den Variabilitätsbereich der Fourier'schen Konstanten von positiven harmonischen Funktionen|journal=Rendiconti del Circolo Matematico di Palermo (1884–1940)|language=de|volume=32|issue=1|pages=193–217[see p.200 bottom]|doi=10.1007/BF03014795|year=1911|s2cid=120032616|url=https://link.springer.com/article/10.1007%2FBF03014795}}</ref> In 1914 [[Ernst Steinitz]] expanded Carathéodory's theorem for arbitrary sets.<ref>{{cite journal
|last=Steinitz
|first=Ernst
|author-link=Ernst Steinitz
|title=Bedingt konvergente Reihen und konvexe Systeme
|journal=J. Reine Angew. Math.
|volume=1913
|year=1913
|pages=128–175
|doi=10.1515/crll.1913.143.128
|issue=143
|s2cid=120411668
}}</ref>
<!-- *'''TO DO''': state/quote [3]'s formulation of theorem --> <!-- *'''TO DO''': state/quote [4]'s formulation of theorem-->

== Example ==
[[Image:Caratheodorys theorem example.svg|thumb|280px|An illustration of Carathéodory's theorem for a square in '''R'''<sup>2</sup>]]
Carathéodory's theorem in 2 dimensions states that we can construct a triangle consisting of points from ''P'' that encloses any point in the convex hull of ''P''.

For example, let ''P'' = {(0,0), (0,1), (1,0), (1,1)}. The convex hull of this set is a square. Let ''x'' = (1/4, 1/4) in the convex hull of ''P''. We can then construct a set {(0,0),(0,1),(1,0)} = {{italics correction|''P''}}&prime;, the convex hull of which is a triangle and encloses ''x.''

==Proof== 
'''Note:''' We will only use the fact that <math>\R</math> is an [[ordered field]], so the theorem and proof works even when <math>\R</math> is replaced by any field <math>\mathbb F</math>, together with a total order.


We first formally state Carathéodory's theorem:<ref>{{Cite book |last=Leonard |first=I. Ed |title=Geometry of convex sets |last2=Lewis |first2=J. E. |date=2016 |publisher=Wiley Blackwell |isbn=978-1-119-02266-4 |location=Hoboken, New Jersey |chapter=3.3 Convex Hulls}}</ref>
{{Math theorem
| name = Carathéodory's theorem
| note = 
| math_statement = If <math>x \in \mathrm{Cone}(S) \subset \R^d</math>, then <math>x</math> is the nonnegative sum of at most <math>d</math> points of <math>S</math>.  

If <math>x \in \mathrm{Conv}(S) \subset \R^d</math>, then <math>x</math> is the convex sum of at most <math>d+1</math> points of <math>S</math>.
}}
The essence of Carathéodory's theorem is in the finite case. This reduction to the finite case is possible because <math>\mathrm{Conv}(S)</math> is the set of ''finite'' convex combination of elements of <math>S</math> (see the [[convex hull]] page for details).

{{Math theorem
| name = Lemma
| note = 
| math_statement = If <math>q_1, ..., q_N \in \R^d</math> then <math>\forall x \in \mathrm{Conv}(\{q_1, ..., q_N\})</math>, exists <math>w_1, ..., w_N \geq 0</math> such that <math>x = \sum_n w_n q_n</math>, and at most <math>d</math> of them are nonzero.
}}With the lemma, Carathéodory's theorem is a simple extension:
{{Math proof|title=Proof of Carathéodory's theorem|proof=  

For any <math>x\in \mathrm{Conv}(S)</math>, represent <math>x=\sum_{n=1}^N w_n q_n</math> for some <math>q_1, ..., q_N\in S</math>, then <math>x\in \mathrm{Conv}(\{q_1, ..., q_N\})</math>, and we use the lemma.

The second part{{Clarify|date=April 2024|reason=In the proof, there is a mention of two parts. The first part, which concerns the "Cone", has not been treated. The connection between the two parts ("Cone" and "Conv") is not clear.}} reduces to the first part by "lifting up one dimension", a common trick used  to reduce affine geometry to linear algebra, and reduce convex bodies to convex cones.  

Explicitly, let <math>S\subset \R^d</math>, then identify <math>\R^d</math> with the subset <math>\{w \in \R^{d+1}: w_{d+1} = 1\}</math>. This induces an embedding of <math>S</math> into <math>S \times \{1\}\subset \R^{d+1}</math>.  

Any <math>x\in S</math>, by first part, has a "lifted" representation <math>(x, 1) = \sum_{n=1}^N w_n (q_n, 1)</math> where at most <math>d+1</math> of <math>w_n</math> are nonzero. That is, <math>x = \sum_{n=1}^N w_n q_n</math>, and <math>1 =\sum_{n=1}^N w_n</math>, which completes the proof.  

}}

{{Math proof|title=Proof of lemma|proof=  

This is trivial when <math>N \leq d</math>. If we can prove it for all <math>N = d+1</math>, then by induction we have proved it for all <math>N \geq d+1</math>. Thus it remains to prove it for <math>N = d+1</math>. This we prove by induction on <math>d</math>.  

Base case: <math>d=1, N = 2</math>, trivial.  

Induction case. Represent <math>x = \sum_{n=1}^{d+1} w_n q_n</math>. If some <math> w_n = 0</math>, then the proof is finished. So assume all <math>w_n > 0</math>

If <math>\{q_1, ..., q_{d}\}</math> is linearly dependent, then we can use induction on its linear span to eliminate one nonzero term in <math>\sum_{n=1}^d \frac{w_n}{w_1 + \cdots + w_d}q_n</math>, and thus eliminate it in  <math>x = \sum_{n=1}^{d+1} w_n q_n</math> as well.

Else, there exists <math>(u_1, ..., u_{d}) \in \R^{d}</math>, such that <math>\sum_{n=1}^{d} u_n q_n = q_{d+1}</math>. Then we can interpolate a full interval of representations:  

<math display="block">x = \sum_{n=1}^{d} (w_n+ \theta w_{d+1}u_n) q_n + (1-\theta) w_{d+1} q_{d+1}; \quad \theta\in[0, 1]</math>

If <math>w_n + w_{d+1} u_n \geq 0</math> for all <math>n=1, ..., d</math>, then set <math>\theta = 1</math>. Otherwise, let <math>\theta</math> be the smallest <math>\theta</math> such that one of <math>w_n + \theta w_{d+1} u_n = 0</math>. Then we obtain a convex representation of <math>x</math> with <math>\leq d</math> nonzero terms.  
}}

Alternative proofs use [[Helly's theorem]] or the [[Perron–Frobenius theorem]].<ref>{{Cite book|url=http://ebooks.cambridge.org/ref/id/CBO9780511566172|title=Convexity|last=Eggleston|first=H. G.|publisher=Cambridge University Press|year=1958|doi=10.1017/cbo9780511566172|isbn=9780511566172}} See pages 40–41.</ref><ref>{{Cite journal|arxiv=1901.00540|first1=Márton|last1=Naszódi|first2=Alexandr|last2=Polyanskii|title=Perron and Frobenius Meet Carathéodory|journal=The Electronic Journal of Combinatorics|year=2021|volume=28|issue=3|doi=10.37236/9996|s2cid=119656227}}</ref>

== Variants ==

=== Carathéodory's number ===
For any nonempty <math>P\subset \R^d</math>, define its '''Carathéodory's number''' to be the smallest integer <math>r</math>, such that for any <math>x\in \mathrm{Conv}(P)</math>, there exists a representation of <math>x</math> as a convex sum of up to <math>r</math> elements in <math>P</math>.

Carathéodory's theorem simply states that any nonempty subset of <math>\R^d</math> has Carathéodory's number <math>\leq d+1</math>. This upper bound is not necessarily reached. For example, the unit sphere in <math>\R^d</math> has Carathéodory's number equal to 2, since any point inside the sphere is the convex sum of two points on the sphere.

With additional assumptions on <math>P\subset \R^d</math>, upper bounds strictly lower than <math>d+1</math> can be obtained.<ref>{{Cite journal |last1=Bárány |first1=Imre |last2=Karasev |first2=Roman |date=2012-07-20 |title=Notes About the Carathéodory Number |journal=Discrete & Computational Geometry |language=en |volume=48 |issue=3 |pages=783–792 |arxiv=1112.5942 |doi=10.1007/s00454-012-9439-z |issn=0179-5376 |s2cid=9090617}}</ref>
=== Dimensionless variant ===
Recently, Adiprasito, Barany, Mustafa and Terpai proved a variant of Caratheodory's theorem that does not depend on the dimension of the space.<ref>{{cite arXiv|last1=Adiprasito|first1=Karim|last2=Bárány|first2=Imre|last3=Mustafa|first3=Nabil H.|last4=Terpai|first4=Tamás|date=2019-08-28|title=Theorems of Carathéodory, Helly, and Tverberg without dimension|class=math.MG|eprint=1806.08725}}</ref>

=== {{Anchor|colorful}}Colorful Carathéodory theorem ===
Let ''X''<sub>1</sub>, ..., ''X''<sub>''d''+1</sub> be sets in '''R'''<sup>''d''</sup> and let ''x'' be a point contained in the intersection of the convex hulls of all these ''d''+1 sets.

Then there is a set ''T'' = {''x''<sub>1</sub>, ..., ''x''<sub>''d''+1</sub>}, where {{math|''x''<sub>1</sub> ∈ ''X''<sub>1</sub>, ..., ''x''<sub>''d''+1</sub> ∈ ''X''<sub>''d''+1</sub>}}, such that the convex hull of ''T'' contains the point ''x''.<ref name=":0">{{Cite journal|date=1982-01-01|title=A generalization of carathéodory's theorem|journal=Discrete Mathematics|language=en|volume=40|issue=2–3|pages=141–152|doi=10.1016/0012-365X(82)90115-7|issn=0012-365X|last1=Bárány|first1=Imre|doi-access=free}}</ref>

By viewing the sets ''X''<sub>1</sub>, ..., ''X''<sub>''d''+1</sub>  as different colors, the set ''T'' is made by points of all colors, hence the "colorful" in the theorem's name.<ref>{{Cite journal|last1=Montejano|first1=Luis|last2=Fabila|first2=Ruy|last3=Bracho|first3=Javier|last4=Bárány|first4=Imre|last5=Arocha|first5=Jorge L.|date=2009-09-01|title=Very Colorful Theorems|journal=Discrete & Computational Geometry|language=en|volume=42|issue=2|pages=142–154|doi=10.1007/s00454-009-9180-4|issn=1432-0444|doi-access=free}}</ref> The set ''T'' is also called a ''rainbow simplex'', since it is a ''d''-dimensional [[simplex]] in which each corner has a different color.<ref name="Mustafa 1300–1305">{{Cite journal|last1=Mustafa|first1=Nabil H.|last2=Ray|first2=Saurabh|date=2016-04-06|title=An optimal generalization of the Colorful Carathéodory theorem|journal=Discrete Mathematics|language=en|volume=339|issue=4|pages=1300–1305|doi=10.1016/j.disc.2015.11.019|issn=0012-365X|doi-access=free}}</ref>

This theorem has a variant in which the convex hull is replaced by the [[conical hull]].<ref name=":0" />{{Rp|Thm.2.2}}  Let ''X''<sub>1</sub>, ..., ''X''<sub>''d''</sub> be sets in '''R'''<sup>d</sup> and let ''x'' be a point contained in the intersection of the ''conical hulls'' of all these ''d'' sets. Then there is a set ''T'' = {''x''<sub>1</sub>, ..., ''x''<sub>''d''</sub>}, where {{math|''x''<sub>1</sub> ∈ ''X''<sub>1</sub>, ..., ''x''<sub>''d''</sub> ∈ ''X''<sub>''d''</sub>}}, such that the ''conical hull'' of ''T'' contains the point ''x''.<ref name=":0" />

Mustafa and Ray extended this colorful theorem from points to convex bodies.<ref name="Mustafa 1300–1305"/>

The computational problem of finding the colorful set lies in the intersection of the complexity classes [[PPAD (complexity)|PPAD]] and [[PLS (complexity)|PLS]].<ref>{{Citation |last1=Meunier |first1=Frédéric |title=The Rainbow at the End of the Line ? A PPAD Formulation of the Colorful Carathéodory Theorem with Applications |date=2017-01-01 |work=Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |pages=1342–1351 |series=Proceedings |publisher=Society for Industrial and Applied Mathematics |doi=10.1137/1.9781611974782.87 |last2=Mulzer |first2=Wolfgang |last3=Sarrabezolles |first3=Pauline |last4=Stein |first4=Yannik|isbn=978-1-61197-478-2 |s2cid=5784949 |doi-access=free |arxiv=1608.01921 }}</ref>

==See also==

* [[Shapley–Folkman lemma]]
* [[Helly's theorem]]
* [[Kirchberger's theorem]]
* [[N-dimensional polyhedron]]
* [[Radon's theorem]], and its generalization [[Tverberg's theorem]]
* [[Krein–Milman theorem]]
* [[Choquet theory]]

==Notes==
{{reflist}}

==Further reading==
*{{cite book
 | last = Eckhoff | first = J.|ref=none
 | 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}}
*{{Cite journal|last1=Mustafa|first1=Nabil|last2=Meunier|first2=Frédéric|last3=Goaoc|first3=Xavier|last4=De Loera|first4=Jesús|date=2019|title=The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg|journal=Bulletin of the American Mathematical Society|language=en|volume=56|issue=3|pages=415–511|doi=10.1090/bull/1653|issn=0273-0979|arxiv=1706.05975|s2cid=32071768|ref=none}}

==External links==

* [https://planetmath.org/caratheodorystheorem Concise statement of theorem] in terms of convex hulls (at [[PlanetMath]])

{{Convex analysis and variational analysis}}

{{DEFAULTSORT:Caratheodory's theorem (convex hull)}}
[[Category:Articles containing proofs]]
[[Category:Convex hulls]]
[[Category:Geometric transversal theory]]
[[Category:Theorems in convex geometry]]
[[Category:Theorems in discrete geometry]]