Carathéodory's theorem (convex hull)

Carathéodory's theorem (convex hull) Per altri usi, see Carathéodory's theorem (disambiguazione). An illustration of Carathéodory's theorem for a square in R2 Carathéodory's theorem is a theorem in convex geometry. It states that if a point x of Rd 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. Vale a dire, there is a subset P′ of P consisting of d + 1 or fewer points such that x lies in the convex hull of P′. Equivalentemente, x lies in an r-simplex with vertices in P, dove {displaystyle rleq 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.

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, che ha dimostrato il teorema in 1911 for the case when P is compact.[3] In 1914 Ernst Steinitz expanded Carathéodory's theorem for any sets P in Rd.[4] Contenuti 1 Esempio 2 Prova 3 Variants 3.1 Carathéodory's theorem for the conical hull 3.2 Dimensionless variant 3.3 Colorful Carathéodory theorem 4 Guarda anche 5 Appunti 6 Ulteriori letture 7 External links Example Consider a set P = {(0,0), (0,1), (1,0), (1,1)} which is a subset of R2. 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, da |P′| = 3. It may help to visualise Carathéodory's theorem in 2 dimensioni, 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. Quindi, x is a convex combination of a finite number of points in P : {displaystyle mathbf {X} =somma _{j=1}^{K}lambda _{j}mathbf {X} _{j}} where every xj is in P, every λj is (w.l.o.g.) positivo, e {somma dello stile di visualizzazione _{j=1}^{K}lambda _{j}=1} .

Suppose k > d + 1 (altrimenti, non c'è niente da dimostrare). Quindi, the vectors x2 − x1, ..., xk − x1 are linearly dependent, so there are real scalars μ2, ..., μk, not all zero, tale che {somma dello stile di visualizzazione _{j=2}^{K}in _{j}(mathbf {X} _{j}-mathbf {X} _{1})=mathbf {0} .} If μ1 is defined as {displaystyle lui _{1}:=-sum _{j=2}^{K}in _{j}} poi {somma dello stile di visualizzazione _{j=1}^{K}in _{j}mathbf {X} _{j}=mathbf {0} } {somma dello stile di visualizzazione _{j=1}^{K}in _{j}=0} and not all of the μj are equal to zero. Perciò, at least one μj > 0. Quindi, {displaystyle mathbf {X} =somma _{j=1}^{K}lambda _{j}mathbf {X} _{j}-alpha sum _{j=1}^{K}in _{j}mathbf {X} _{j}=somma _{j=1}^{K}(lambda _{j}-alpha mu _{j})mathbf {X} _{j}} for any real α. In particolare, the equality will hold if α is defined as {displaystyle alfa :=min_{1leq jleq k}sinistra{{tfrac {lambda _{j}}{in _{j}}}:in _{j}>0right}={tfrac {lambda _{io}}{in _{io}}}.} Note that α > 0, and for every j between 1 and k, {displaystyle lambda _{j}-alpha mu _{j}geq 0.} In particolare, λi − αμi = 0 by definition of α. Perciò, {displaystyle mathbf {X} =somma _{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 _{io}-alpha mu _{io}=0} . In altre parole, 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 Rd 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. Vale a dire, 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 X1, ..., Xd+1 be sets in Rd 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 = {x1, ..., xd+1}, where x1 ∈ X1, ..., xd+1 ∈ Xd+1, such that the convex hull of T contains the point x.[10] By viewing the sets X1, ..., Xd+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 X1, ..., Xd be sets in Rd 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 = {x1, ..., xd}, where x1 ∈ X1, ..., xd ∈ Xd, such that the conical hull of T contains the point x.[10] Mustafa and Ray extended this colorful theorem from points to convex bodies.[12] The computational problem of finding the colorful set lies in the intersection of the complexity classes PPAD and PLS.[13] See also Shapley–Folkman lemma Helly's theorem Kirchberger's theorem Radon's theorem, and its generalization Tverberg's theorem Krein–Milman theorem Choquet theory Notes ^ 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. S2CID 9090617. ^ Danzer, l.; Grunbaum, B.; Klee, V. (1963). "Helly's theorem and its relatives". Convexity. Proc. Symp. Pure Math. vol. 7. Società matematica americana. pp. 101–179. See in particular p.109 ^ Carathéodory, C. (1911). "Über den Variabilitätsbereich der Fourier'schen Konstanten von positiven harmonischen Funktionen". Rendiconti del Circolo Matematico di Palermo (1884–1940) (in tedesco). 32 (1): 193–217[see p.200 bottom]. doi:10.1007/BF03014795. S2CID 120032616. ^ Steinitz, Ernst (1913). "Bedingt konvergente Reihen und konvexe Systeme". J. Reine Angew. Matematica. 1913 (143): 128–175. doi:10.1515/crll.1913.143.128. S2CID 120411668. ^ Eggleston, H. G. (1958). Convexity. Cambridge University Press. doi:10.1017/cbo9780511566172. ISBN 9780511566172. See pages 40–41. ^ Naszódi, Márton; Polyanskii, Alexandr (2021). "Perron and Frobenius Meet Carathéodory". The Electronic Journal of Combinatorics. 28 (3). arXiv:1901.00540. doi:10.37236/9996. S2CID 119656227. ^ Lovász, Laszló; Plummer, M. D. (1986). Matching Theory. Annals of Discrete Mathematics. vol. 29. Olanda Settentrionale. ISBN 0-444-87916-1. SIG 0859549. ^ "convex geometry - Caratheodory's theorem for vectors in a cone". Mathematics Stack Exchange. Recuperato 2020-07-22. ^ Adiprasito, Karim; Bárány, Imre; Mustafa, Nabil H.; Terpai, Tommaso (2019-08-28). "Theorems of Carathéodory, Helly, and Tverberg without dimension". arXiv:1806.08725 [math.MG]. ^ Salta su: a b c Bárány, Imre (1982-01-01). "A generalization of carathéodory's theorem". Matematica discreta. 40 (2–3): 141–152. doi:10.1016/0012-365X(82)90115-7. ISSN 0012-365X. ^ 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. ^ Salta su: a b Mustafa, Nabil H.; Ray, Saurabh (2016-04-06). "An optimal generalization of the Colorful Carathéodory theorem". Matematica discreta. 339 (4): 1300–1305. doi:10.1016/j.disc.2015.11.019. ISSN 0012-365X. ^ Meunier, Frédéric; Mulzer, Wolfgang; Sarrabezolles, Pauline; Stein, Yannik (2017-01-01), "The Rainbow at the End of the Line ? A PPAD Formulation of the Colorful Carathéodory Theorem with Applications", Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Atti, Society for Industrial and Applied Mathematics, pp. 1342–1351, doi:10.1137/1.9781611974782.87, recuperato 2022-05-03 Further reading Eckhoff, J. (1993). "Helly, Radon, and Carathéodory type theorems". Handbook of Convex Geometry. vol. UN, B. Amsterdam: Olanda Settentrionale. 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". Bollettino dell'American Mathematical Society. 56 (3): 415–511. arXiv:1706.05975. doi:10.1090/bull/1653. ISSN 0273-0979. S2CID 32071768. External links Concise statement of theorem in terms of convex hulls (at PlanetMath) Categorie: Theorems in convex geometryConvex hullsGeometric transversal theoryTheorems in discrete geometry