Carathéodory's theorem (convex hull)

Template:Short description {{#invoke:other uses|otheruses}} 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 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">Template:Cite Lovasz Plummer</ref>Template:Rp

Two other theorems of Helly and Radon are closely related to Carathéodory's theorem: the latter theorem can be used to prove the former theorems and vice versa.<ref>Template:Cite conference 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.<ref>Template:Cite journal</ref> In 1914 Ernst Steinitz expanded Carathéodory's theorem for arbitrary sets.<ref>Template:Cite journal</ref>

Example

File:Caratheodorys theorem example.svg

An illustration of Carathéodory's theorem for a square in R²

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)} = Template:Italics correction′, 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>Template:Cite book</ref> Template:Math theorem 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).

Template:Math theoremWith the lemma, Carathéodory's theorem is a simple extension: Template:Math proof

Alternative proofs use Helly's theorem or the Perron–Frobenius theorem.<ref>Template:Cite book See pages 40–41.</ref><ref>Template:Cite journal</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>Template:Cite journal</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>Template:Cite arXiv</ref>

Template:AnchorColorful Carathéodory theorem

Let X₁, ..., X_d+1 be sets in R^d 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₁, ..., x_d+1}, where Template:Math, such that the convex hull of T contains the point x.<ref name=":0">Template:Cite journal</ref>

By viewing the sets X₁, ..., X_d+1 as different colors, the set T is made by points of all colors, hence the "colorful" in the theorem's name.<ref>Template:Cite journal</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">Template:Cite journal</ref>

This theorem has a variant in which the convex hull is replaced by the conical hull.<ref name=":0" />Template:Rp Let X₁, ..., X_d be sets in R^d 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₁, ..., x_d}, where Template:Math, 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 and PLS.<ref>Template:Citation</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

Further reading

• Template:Cite book
• Template:Cite journal

External links

• Concise statement of theorem in terms of convex hulls (at PlanetMath)