Carathéodory's theorem (convex hull)

Carathéodory's theorem is a theorem in convex geometry. It states that if a point x of R^d lies in the convex hull of a set P, then x can be written as the convex combination of at most d + 1 points in P. Namely, there is a subset P′ of P consisting of d + 1 or fewer points such that x lies in the convex hull of P′. Equivalently, x lies in an r-simplex with vertices in P, where ${\displaystyle r\leq d}$. The smallest r that makes the last statement valid for each x in the convex hull of P is defined as the Carathéodory's number of P. Depending on the properties of P, upper bounds lower than the one provided by Carathéodory's theorem can be obtained.[1] Note that P need not be itself convex. A consequence of this is that P′ can always be extremal in P, as non-extremal points can be removed from P without changing the membership of x in the convex hull.

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

The similar 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.[2]

The result is named for Constantin Carathéodory, who proved the theorem in 1907 for the case when P is compact.[3] In 1914 Ernst Steinitz expanded Carathéodory's theorem for any sets P in R^d.[4]

Example

Consider a set P = {(0,0), (0,1), (1,0), (1,1)} which is a subset of R². The convex hull of this set is a square. Consider now a point x = (1/4, 1/4), which is in the convex hull of P. We can then construct a set {(0,0),(0,1),(1,0)} = P′, the convex hull of which is a triangle and encloses x, and thus the theorem works for this instance, since |P′| = 3. It may help to visualise Carathéodory's theorem in 2 dimensions, as saying that we can construct a triangle consisting of points from P that encloses any point in P.

Proof

Let x be a point in the convex hull of P. Then, x is a convex combination of a finite number of points in P :

${\displaystyle \mathbf {x} =\sum _{j=1}^{k}\lambda _{j}\mathbf {x} _{j}}$

where every x_j is in P, every λ_j is (w.l.o.g.) positive, and ${\displaystyle \sum _{j=1}^{k}\lambda _{j}=1}$.

Suppose k > d + 1 (otherwise, there is nothing to prove). Then, the vectors x₂ − x₁, ..., x_k − x₁ are linearly dependent,

so there are real scalars μ₂, ..., μ_k, not all zero, such that

${\displaystyle \sum _{j=2}^{k}\mu _{j}(\mathbf {x} _{j}-\mathbf {x} _{1})=\mathbf {0} .}$

If μ₁ is defined as

${\displaystyle \mu _{1}:=-\sum _{j=2}^{k}\mu _{j}}$

then

${\displaystyle \sum _{j=1}^{k}\mu _{j}\mathbf {x} _{j}=\mathbf {0} }$

${\displaystyle \sum _{j=1}^{k}\mu _{j}=0}$

and not all of the μ_j are equal to zero. Therefore, at least one μ_j > 0. Then,

${\displaystyle \mathbf {x} =\sum _{j=1}^{k}\lambda _{j}\mathbf {x} _{j}-\alpha \sum _{j=1}^{k}\mu _{j}\mathbf {x} _{j}=\sum _{j=1}^{k}(\lambda _{j}-\alpha \mu _{j})\mathbf {x} _{j}}$

for any real α. In particular, the equality will hold if α is defined as

${\displaystyle \alpha$ :=\min _{1\leq j\leq k}\left\{{\tfrac {\lambda _{j}}{\mu _{j}}}:\mu _{j}>0\right\}={\tfrac {\lambda _{i}}{\mu _{i}}}.}

Note that α > 0, and for every j between 1 and k,

${\displaystyle \lambda _{j}-\alpha \mu _{j}\geq 0.}$

In particular, λ_i − αμ_i = 0 by definition of α. Therefore,

${\displaystyle \mathbf {x} =\sum _{j=1}^{k}(\lambda _{j}-\alpha \mu _{j})\mathbf {x} _{j}}$

where every ${\displaystyle \lambda _{j}-\alpha \mu _{j}}$ is nonnegative, their sum is one , and furthermore, ${\displaystyle \lambda _{i}-\alpha \mu _{i}=0}$. In other words, x is represented as a convex combination of at most k-1 points of P. This process can be repeated until x is represented as a convex combination of at most d + 1 points in P.

Alternative proofs uses Helly's theorem or the Perron–Frobenius theorem.[5][6]

Variants

Carathéodory's theorem for the conical hull

If a point x of R^d lies in the conical hull of a set P, then x can be written as the conical combination of at most d points in P. Namely, there is a subset P′ of P consisting of d or fewer points, such that x lies in the conical hull of P′.[7]^:257 The proof is similar to the original theorem; the difference is that, in a d-dimensional space, the maximum size of a linearly-independent set is d, while the maximum size of an affinely-independent set is d+1.[8]

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.[9]

Colorful 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 x₁ ∈ X₁, ..., x_d+1 ∈ X_d+1, such that the convex hull of T contains the point x.[10]

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.[11] The set T is also called a rainbow simplex, since it is a d-dimensional simplex in which each corner has a different color.[12]

This theorem has a variant in which the convex hull is replaced by the conical hull.[10]^:Thm.2.2 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 x₁ ∈ X₁, ..., x_d+1 ∈ X_d+1, such that the conical hull of T contains the point x.[10]

Mustafa and Ray extended this colorful theorem from points to convex bodies.[13]

See also

• Shapley–Folkman lemma
• Helly's theorem
• Radon's theorem, and its generalization Tverberg's theorem
• Krein–Milman theorem
• Choquet theory

Notes

1. Bárány, Imre; Karasev, Roman (2012-07-20). "Notes About the Carathéodory Number". Discrete & Computational Geometry. 48 (3): 783–792. arXiv:1112.5942. doi:10.1007/s00454-012-9439-z. ISSN 0179-5376.
2. Danzer, L.; Grünbaum, B.; Klee, V. (1963). "Helly's theorem and its relatives". Convexity. Proc. Symp. Pure Math. 7. American Mathematical Society. pp. 101–179. See in particular p.109
3. Carathéodory, C. (1907). "Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen". Mathematische Annalen (in German). 64 (1): 95–115. doi:10.1007/BF01449883. ISSN 0025-5831. MR 1511425.
4. Steinitz, Ernst (1913). "Bedingt konvergente Reihen und konvexe Systeme". J. Reine Angew. Math. 1913 (143): 128–175. doi:10.1515/crll.1913.143.128.
5. Eggleston, H. G. (1958). Convexity. Cambridge University Press. doi:10.1017/cbo9780511566172. ISBN 9780511566172. See pages 40–41.
6. Naszódi, Márton; Polyanskii, Alexandr (2019). "Perron and Frobenius meet Carathéodory". arXiv:1901.00540 [math.MG].
7. Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
8. "convex geometry - Caratheodory's theorem for vectors in a cone". Mathematics Stack Exchange. Retrieved 2020-07-22.
9. Adiprasito, Karim; Bárány, Imre; Mustafa, Nabil H.; Terpai, Tamás (2019-08-28). "Theorems of Carath\'eodory, Helly, and Tverberg without dimension". arXiv:1806.08725 [cs, math].
10. Bárány, Imre (1982-01-01). "A generalization of carathéodory's theorem". Discrete Mathematics. 40 (2–3): 141–152. doi:10.1016/0012-365X(82)90115-7. ISSN 0012-365X.
11. Montejano, Luis; Fabila, Ruy; Bracho, Javier; Bárány, Imre; Arocha, Jorge L. (2009-09-01). "Very Colorful Theorems". Discrete & Computational Geometry. 42 (2): 142–154. doi:10.1007/s00454-009-9180-4. ISSN 1432-0444.
12. Mustafa, Nabil H.; Ray, Saurabh (2016-04-06). "An optimal generalization of the Colorful Carathéodory theorem". Discrete Mathematics. 339 (4): 1300–1305. doi:10.1016/j.disc.2015.11.019. ISSN 0012-365X.
13. Mustafa, Nabil H.; Ray, Saurabh (2016-04-06). "An optimal generalization of the Colorful Carathéodory theorem". Discrete Mathematics. 339 (4): 1300–1305. doi:10.1016/j.disc.2015.11.019. ISSN 0012-365X.

Further reading

• Eckhoff, J. (1993), "Helly, Radon, and Carathéodory type theorems", Handbook of Convex Geometry, A, B, Amsterdam: North-Holland, pp. 389–448.
• Mustafa, Nabil; Meunier, Frédéric; Goaoc, Xavier; De Loera, Jesús (2019). "The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg". Bulletin of the American Mathematical Society. 56 (3): 415–511. arXiv:1706.05975. doi:10.1090/bull/1653. ISSN 0273-0979.

External links

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