El teorema de Carathéodory es un teorema de geometría convexa . Establece que si un punto x de R d se encuentra en el casco convexo de un conjunto P , entonces x puede escribirse como la combinación convexa de como máximo d + 1 puntos en P. Es decir, hay un subconjunto P ′ de P que consiste de d + 1 o menos puntos de manera que x se encuentra en el casco convexo de P ′. De manera equivalente, x se encuentra en un r - simplex con vértices en P , donde. La r más pequeña que hace que la última declaración sea válida para cada x en el casco convexo de P se define como el número de P de Carathéodory . Dependiendo de las propiedades de P , se pueden obtener límites superiores inferiores a los proporcionados por el teorema de Carathéodory. [1] Nótese que P no necesita ser convexo en sí mismo. Una consecuencia de esto es que P ′ siempre puede ser extremo en P , ya que los puntos no extremos pueden eliminarse de P sin cambiar la pertenencia de x en el casco convexo.
Los teoremas similares de Helly y Radon están estrechamente relacionados con el teorema de Carathéodory: el último teorema puede usarse para probar los primeros teoremas y viceversa. [2]
El resultado lleva el nombre de Constantin Carathéodory , quien demostró el teorema en 1907 para el caso en que P es compacto. [3] En 1914 Ernst Steinitz amplió el teorema de Carathéodory para cualquier conjunto P en R d . [4]
Ejemplo
Considere un conjunto P = {(0,0), (0,1), (1,0), (1,1)} que es un subconjunto de R 2 . El casco convexo de este conjunto es un cuadrado. Consideremos ahora un punto x = (1/4, 1/4), que se encuentra en el casco convexo de P . Entonces podemos construir un conjunto {(0,0), (0,1), (1,0)} = P ′, cuyo casco convexo es un triángulo y encierra x , y así el teorema funciona para este caso, desde | P ′ | = 3. Se puede ayudar a visualizar el teorema de Carathéodory en 2 dimensiones, como diciendo que podemos construir un triángulo formado por los puntos de P que encierra cualquier punto en P .
Prueba
Vamos x ser un punto en el casco convexo de P . Entonces, x es una combinación convexa de un número finito de puntos en P :
donde cada x j está en P , cada λ j es (wlog) positivo, y.
Suponga que k > d + 1 (de lo contrario, no hay nada que probar). Entonces, los vectores x 2 - x 1 , ..., x k - x 1 son linealmente dependientes ,
así que hay escalares reales μ 2 , ..., μ k , no todos cero, de modo que
Si μ 1 se define como
luego
y no todos los μ j son iguales a cero. Por lo tanto, al menos un μ j > 0. Entonces,
para cualquier α real . En particular, la igualdad se mantendrá si α se define como
Tenga en cuenta que α > 0, y para todo j entre 1 y k ,
En particular, λ i - αμ i = 0 por definición de α . Por lo tanto,
donde cada no es negativo, su suma es uno y, además, . En otras palabras, x se representa como una combinación convexa de en la mayoría de k -1 puntos de P . Este proceso puede repetirse hasta que x se representa como una combinación convexa de en la mayoría d + 1 puntos en P .
Las demostraciones alternativas utilizan el teorema de Helly o el teorema de Perron-Frobenius . [5] [6]
Variantes
Teorema de Carathéodory para el casco cónico
Si un punto x de R d se encuentra en el casco cónico de un conjunto P , entonces x puede escribirse como la combinación cónica de como máximo d puntos en P. Es decir, hay un subconjunto P ′ de P que consta de d o menos puntos , de manera que x se encuentra en el casco cónico de P ′. [7] : 257 La demostración es similar al teorema original; la diferencia es que, en un espacio d -dimensional, el tamaño máximo de un conjunto linealmente independiente es d , mientras que el tamaño máximo de un conjunto afinamente independiente es d +1. [8]
Variante adimensional
Recientemente, Adiprasito, Barany, Mustafa y Terpai demostraron una variante del teorema de Caratheodory que no depende de la dimensión del espacio. [9]
Teorema de Carathéodory colorido
Sea X 1 , ..., X d + 1 conjuntos en R d y sea x un punto contenido en la intersección de los cascos convexos de todos estos d +1 conjuntos.
Entonces hay un conjunto T = { x 1 , ..., x d + 1 }, donde x 1 ∈ X 1 , ..., x d + 1 ∈ X d + 1 , tal que el casco convexo de T contiene el punto x . [10]
Al ver los conjuntos X 1 , ..., X d + 1 como colores diferentes, el conjunto T está formado por puntos de todos los colores, de ahí el "colorido" en el nombre del teorema. [11] El conjunto T también se denomina simplex arcoíris , ya que es un simplex d- dimensional en el que cada esquina tiene un color diferente. [12]
Este teorema tiene una variante en la que el casco convexo se reemplaza por el casco cónico . [10] : Thm.2.2 Sean X 1 , ..., X d conjuntos en R d y sea x un punto contenido en la intersección de los cascos cónicos de todos estos d conjuntos. Entonces hay un conjunto T = { x 1 , ..., x d }, donde x 1 ∈ X 1 , ..., x d + 1 ∈ X d + 1 , tal que el casco cónico de T contiene el punto x . [10]
Mustafa y Ray extendieron este colorido teorema de puntos a cuerpos convexos. [12]
Ver también
Notas
- ^ Bárány, Imre; Karasev, Roman (20 de julio de 2012). "Notas sobre el número Carathéodory". Geometría discreta y computacional . 48 (3): 783–792. arXiv : 1112.5942 . doi : 10.1007 / s00454-012-9439-z . ISSN 0179-5376 . S2CID 9090617 .
- ^ Danzer, L .; Grünbaum, B .; Klee, V. (1963). "Teorema de Helly y sus parientes". Convexidad . Proc. Symp. Matemática pura. 7 . Sociedad Matemática Estadounidense . págs. 101-179. Ver en particular la p.109
- ^ Carathéodory, C. (1907). "Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen" . Mathematische Annalen (en alemán). 64 (1): 95-115. doi : 10.1007 / BF01449883 . ISSN 0025-5831 . Señor 1511425 . S2CID 116695038 .
- ^ Steinitz, Ernst (1913). "Bedingt konvergente Reihen und konvexe Systeme". J. Reine Angew. Matemáticas . 1913 (143): 128-175. doi : 10.1515 / crll.1913.143.128 . S2CID 120411668 .
- ^ Eggleston, HG (1958). Convexidad . Prensa de la Universidad de Cambridge. doi : 10.1017 / cbo9780511566172 . ISBN 9780511566172. Consulte las páginas 40–41.
- ^ Naszódi, Márton; Polyanskii, Alexandr (2019). "Perron y Frobenius conocen a Carathéodory". arXiv : 1901.00540 [ math.MG ].
- ^ Lovász, László ; Plummer, MD (1986). Teoría de emparejamiento . Annals of Discrete Mathematics. 29 . Holanda Septentrional. ISBN 0-444-87916-1. Señor 0859549 .
- ^ "geometría convexa - teorema de Caratheodory para vectores en un cono" . Intercambio de pila de matemáticas . Consultado el 22 de julio de 2020 .
- ^ Adiprasito, Karim; Bárány, Imre; Mustafa, Nabil H .; Terpai, Tamás (28 de agosto de 2019). "Teoremas de Carathéodory, Helly y Tverberg sin dimensión". arXiv : 1806.08725 [ math.MG ].
- ^ a b c Bárány, Imre (1 de enero de 1982). "Una generalización del teorema de carathéodory". Matemáticas discretas . 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. (1 de septiembre de 2009). "Teoremas muy coloridos" . Geometría discreta y computacional . 42 (2): 142-154. doi : 10.1007 / s00454-009-9180-4 . ISSN 1432-0444 .
- ^ a b Mustafa, Nabil H .; Ray, Saurabh (6 de abril de 2016). "Una generalización óptima del teorema de Carathéodory colorido" . Matemáticas discretas . 339 (4): 1300-1305. doi : 10.1016 / j.disc.2015.11.019 . ISSN 0012-365X .
Otras lecturas
- Eckhoff, J. (1993). "Teoremas de tipo Helly, Radon y Carathéodory". Manual de geometría convexa . A, B . Amsterdam: Holanda Septentrional. págs. 389–448.
- Mustafa, Nabil; Meunier, Frédéric; Goaoc, Xavier; De Loera, Jesús (2019). "Los teoremas discretos pero ubicuos de Carathéodory, Helly, Sperner, Tucker y Tverberg". Boletín de la American Mathematical Society . 56 (3): 415–511. arXiv : 1706.05975 . doi : 10.1090 / toro / 1653 . ISSN 0273-0979 . S2CID 32071768 .
enlaces externos
- Declaración concisa del teorema en términos de cascos convexos (en PlanetMath )