El teorema de Carathéodory es una proposición sobre geometría convexa. Establece que si un punto se encuentra en la envolvente convexa de un conjunto , entonces pertenece a algún símplex de dimensión con vértices en . De manera equivalente, puede expresarse como la combinación convexa de puntos o menos de . Además, puede escribirse como la combinación convexa de, a lo sumo, puntos extremos de , ya que los puntos no extremos pueden eliminarse de sin alterar la pertenencia de a la envolvente convexa.
Un teorema equivalente para combinaciones cónicas establece que si un punto se encuentra en la combinación cónica de un conjunto , entonces puede expresarse como la combinación cónica de, a lo sumo, puntos de . Lovász, László; Plummer, M. D. (1986). Matching Theory. Annals of Discrete Mathematics. Vol. 29. North-Holland. ISBN 0-444-87916-1. MR 0859549.
Otros dos teoremas de Helly y de Radon están estrechamente relacionados con el teorema de Carathéodory: este último puede utilizarse para demostrar los anteriores, y viceversa. Véase en particular p.109
El resultado lleva el nombre de Constantin Carathéodory, quien demostró el teorema en 1911 para el caso en que es compacto. En 1914, Ernst Steinitz amplió el teorema de Carathéodory a conjuntos arbitrarios.
Ejemplo
El teorema de Carathéodory en 2 dimensiones establece que se puede construir un triángulo formado por puntos de P que encierre cualquier punto de la envolvente convexa de P.
Por ejemplo, sea P = {(0,0), (0,1), (1,0), (1,1)}. La envolvente convexa de este conjunto es un cuadrado. Sea x = (1/4, 1/4) un punto en la envolvente convexa de P. Entonces, se puede construir el conjunto {(0,0),(0,1),(1,0)} = P ′, cuya envolvente convexa es un triángulo que contiene a x.
Demostración Nota: Solo se utiliza el hecho de que es un cuerpo ordenado, por lo que el teorema y la demostración son válidos incluso si se sustituye por cualquier cuerpo dotado de un orden total.
En primer lugar, se enuncia formalmente el teorema de Carathéodory:
La esencia del teorema de Carathéodory reside en el caso finito. Esta reducción al caso finito es posible porque es el conjunto de combinaciones convexas finitas de elementos de (véase la página envolvente convexa para más detalles).
Con el lema, el teorema de Carathéodory resulta ser una extensión sencilla:
Otras demostraciones utilizan el teorema de Helly o el teorema de Perron-Frobenius. See pages 40–41.
Variantes
Número de Carathéodory Para cualquier conjunto no vacío , se define su número de Carathéodory como el entero más pequeño tal que, para cualquier , existe una representación de como una combinación convexa de hasta elementos de .
El teorema de Carathéodory establece simplemente que cualquier subconjunto no vacío de tiene un número de Carathéodory . Esta cota superior no se alcanza necesariamente. Por ejemplo, la esfera unidad en tiene un número de Carathéodory igual a 2, ya que cualquier punto dentro de la esfera es una combinación convexa de dos puntos de la esfera.
Con suposiciones adicionales sobre , se pueden obtener cotas superiores estrictamente menores que .
Variante independiente de la dimensión Son bien conocidos los resultados del tipo del teorema de Carathéodory en los que el diámetro sustituye a la dependencia de la dimensión. Barman proporcionó un enunciado explícito de un teorema de Carathéodory independiente de la dimensión. Es probable que este teorema se hubiera formulado mucho antes, ya que es una consecuencia sencilla del análisis del algoritmo del perceptrón de Novikoff. Concretamente, para todo entero positivo y todo punto dentro de la envolvente convexa de un conjunto finito de puntos , existe un subconjunto de puntos tal que el punto dado se encuentra a una distancia de la envolvente convexa de .
Teorema colorido de Carathéodory Sean X1, ..., Xd+1 conjuntos en Rd y sea x un punto contenido en la intersección de las envolventes convexas de todos estos d+1 conjuntos.
Entonces existe un conjunto T = {x1, ..., xd+1}, donde , tal que la envolvente convexa de T contiene al punto x.
Al considerar los conjuntos X1, ..., Xd+1 como colores diferentes, el conjunto T está formado por puntos de todos los colores; de ahí el término "colorido" en el nombre del teorema. El conjunto T también se denomina símplice arcoíris, ya que es un símplex de dimensión d en el que cada vértice tiene un color diferente.
Este teorema tiene una variante en la que la envolvente convexa se sustituye por la combinación cónica. Sean X1, ..., Xd conjuntos en Rd y sea x un punto contenido en la intersección de las envolventes cónicas de todos estos conjuntos d. Entonces existe un conjunto T = {x1, ..., xd}, donde , tal que la envolvente cónica de T contiene al punto x.
Mustafa y Ray extendieron este teorema colorido de puntos a cuerpos convexos.
El problema computacional de hallar el conjunto colorido se sitúa en la intersección de las clases de complejidad PPAD y PLS.
Véase también Lema de Shapley–Folkman Teorema de Helly Teorema de Kirchberger Poliedro n dimensional Lema de Radon, y su generalización, el teorema de Tverberg Teorema de Krein-Milman Teoría de Choquet
Referencias
Lecturas adicionales
Enlaces externos Enunciado conciso del teorema en términos de envolventes convexas (en PlanetMath)
Categoría:Envolventes convexas Categoría:Teoría de transversales geométricas Categoría:Teoremas en geometría convexa Categoría:Teoremas en geometría discreta