Teorema de Carathéodory (envolvente convexa)

Punto en la envoltura convexa de un conjunto P en Rd, es la combinación convexa de d+1 puntos en P

El teorema de Carathéodory es un teorema de geometría convexa . Afirma que si un punto se encuentra en la envoltura convexa de un conjunto , entonces se encuentra en algún símplex de dimensión 1 con vértices en . De manera equivalente, se puede escribir como la combinación convexa de como máximo puntos en . Además, se puede escribir como la combinación convexa de como máximo puntos extremos en , ya que los puntos no extremos se pueden eliminar de sin cambiar la pertenencia de en la envoltura convexa. ${\displaystyle x}$ ${\displaystyle \mathrm {Conv} (P)}$ ${\displaystyle P\subset \mathbb {R} ^{d}}$ ${\displaystyle x}$ ${\displaystyle d}$ ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle d+1}$ ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle d+1}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle x}$

Un teorema equivalente para combinaciones cónicas establece que si un punto se encuentra en la envoltura cónica de un conjunto , entonces puede escribirse como la combinación cónica de como máximo puntos en . ^{[1] : 257} ${\displaystyle x}$ ${\displaystyle \mathrm {Cone} (P)}$ ${\displaystyle P\subset \mathbb {R} ^{d}}$ ${\displaystyle x}$ ${\displaystyle d}$ ${\displaystyle P}$

Otros dos teoremas de Helly y Radon están estrechamente relacionados con el teorema de Carathéodory: el último teorema puede usarse para demostrar los teoremas anteriores y viceversa. ^[2]

El resultado debe su nombre a Constantin Carathéodory , quien demostró el teorema en 1911 para el caso en que es compacto . ^[3] En 1914 Ernst Steinitz amplió el teorema de Carathéodory para conjuntos arbitrarios. ^[4] ${\displaystyle P}$

Ejemplo

Una ilustración del teorema de Carathéodory para un cuadrado en R ²

El teorema de Carathéodory en dos dimensiones establece que podemos construir un triángulo formado por puntos de P que encierra cualquier punto de la envoltura convexa de P.

Por ejemplo, sea P = {(0,0), (0,1), (1,0), (1,1)}. La envoltura convexa de este conjunto es un cuadrado. Sea x = (1/4, 1/4) en la envoltura convexa de P . Podemos entonces construir un conjunto {(0,0),(0,1),(1,0)} = P ′, cuya envoltura convexa es un triángulo y encierra a x.

Prueba

Nota: Solo utilizaremos el hecho de que es un campo ordenado , por lo que el teorema y la prueba funcionan incluso cuando se reemplaza por cualquier campo , junto con un orden total. ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {F} }$

En primer lugar enunciamos formalmente el teorema de Carathéodory: ^[5]

Teorema de Carathéodory  :  Si , entonces es la suma no negativa de en la mayoría de los puntos de . ${\displaystyle x\in \mathrm {Cone} (S)\subset \mathbb {R} ^{d}}$ ${\displaystyle x}$ ${\displaystyle d}$ ${\displaystyle S}$

Si , entonces es la suma convexa de en la mayoría de los puntos de . ${\displaystyle x\in \mathrm {Conv} (S)\subset \mathbb {R} ^{d}}$ ${\displaystyle x}$ ${\displaystyle d+1}$ ${\displaystyle S}$

La esencia del teorema de Carathéodory se encuentra en el caso finito. Esta reducción al caso finito es posible porque es el conjunto de combinaciones convexas finitas de elementos de (consulte la página de envoltura convexa para obtener más detalles). ${\displaystyle \mathrm {Conv} (S)}$ ${\displaystyle S}$

Lema  —  Si entonces , existe tal que , y como máximo de ellos son distintos de cero. ${\displaystyle q_{1},...,q_{N}\in \mathbb {R} ^{d}}$ ${\displaystyle \forall x\in \mathrm {Conv} (\{q_{1},...,q_{N}\})}$ ${\displaystyle w_{1},...,w_{N}\geq 0}$ ${\displaystyle x=\sum _{n}w_{n}q_{n}}$ ${\displaystyle d}$

Con el lema, el teorema de Carathéodory es una extensión simple:

Demostración del teorema de Carathéodory

Para cualquier , representamos para algún , entonces , y usamos el lema. ${\displaystyle x\in \mathrm {Conv} (S)}$ ${\displaystyle x=\sum _{n=1}^{N}w_{n}q_{n}}$ ${\displaystyle q_{1},...,q_{N}\in S}$ ${\displaystyle x\in \mathrm {Conv} (\{q_{1},...,q_{N}\})}$

La segunda parte ^{[ aclaración necesaria ]} se reduce a la primera parte "levantando una dimensión", un truco común utilizado para reducir la geometría afín al álgebra lineal y reducir los cuerpos convexos a conos convexos.

Explícitamente, sea , entonces identifíquese con el subconjunto . Esto induce una incrustación de en . ${\displaystyle S\subset \mathbb {R} ^{d}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle \{w\in \mathbb {R} ^{d+1}:w_{d+1}=1\}}$ ${\displaystyle S}$ ${\displaystyle S\times \{1\}\subset \mathbb {R} ^{d+1}}$

Cualquier , por primera parte, tiene una representación "elevada" donde como máximo son distintos de cero. Es decir, , y , lo que completa la prueba. ${\displaystyle x\in S}$ ${\displaystyle (x,1)=\sum _{n=1}^{N}w_{n}(q_{n},1)}$ ${\displaystyle d+1}$ ${\displaystyle w_{n}}$ ${\displaystyle x=\sum _{n=1}^{N}w_{n}q_{n}}$ ${\displaystyle 1=\sum _{n=1}^{N}w_{n}}$

Prueba del lema

Esto es trivial cuando . Si podemos probarlo para todos , entonces por inducción lo hemos probado para todos . Por lo tanto, queda probarlo para . Esto lo demostramos por inducción en . ${\displaystyle N\leq d}$ ${\displaystyle N=d+1}$ ${\displaystyle N\geq d+1}$ ${\displaystyle N=d+1}$ ${\displaystyle d}$

Caso base: , trivial. ${\displaystyle d=1,N=2}$

Caso de inducción. Representa . Si algún , entonces la prueba está terminada. Por lo tanto, supongamos que todos ${\displaystyle x=\sum _{n=1}^{d+1}w_{n}q_{n}}$ ${\displaystyle w_{n}=0}$ ${\displaystyle w_{n}>0}$

Si es linealmente dependiente, entonces podemos usar la inducción en su intervalo lineal para eliminar un término distinto de cero en , y así eliminarlo también en . ${\displaystyle \{q_{1},...,q_{d}\}}$ ${\displaystyle \sum _{n=1}^{d}{\frac {w_{n}}{w_{1}+\cdots +w_{d}}}q_{n}}$ ${\displaystyle x=\sum _{n=1}^{d+1}w_{n}q_{n}}$

De lo contrario, existe tal que . Entonces podemos interpolar un intervalo completo de representaciones: ${\displaystyle (u_{1},...,u_{d})\in \mathbb {R} ^{d}}$ ${\displaystyle \sum _{n=1}^{d}u_{n}q_{n}=q_{d+1}}$

$${\displaystyle x=\sum _{n=1}^{d}(w_{n}+\theta w_{d+1}u_{n})q_{n}+(1-\theta )w_{d+1}q_{d+1};\quad \theta \in [0,1]}$$

Si para todos , entonces . En caso contrario, sea el más pequeño tal que uno de . Entonces obtenemos una representación convexa de con términos distintos de cero. ${\displaystyle w_{n}+w_{d+1}u_{n}\geq 0}$ ${\displaystyle n=1,...,d}$ ${\displaystyle \theta =1}$ ${\displaystyle \theta }$ ${\displaystyle \theta }$ ${\displaystyle w_{n}+\theta w_{d+1}u_{n}=0}$ ${\displaystyle x}$ ${\displaystyle \leq d}$

Las pruebas alternativas utilizan el teorema de Helly o el teorema de Perron-Frobenius . ^{[6] [7]}

Variantes

El número de Carathéodory

Para cualquier no vacío , defina su número de Carathéodory como el entero más pequeño , tal que para cualquier , existe una representación de como una suma convexa de hasta elementos en . ${\displaystyle P\subset \mathbb {R} ^{d}}$ ${\displaystyle r}$ ${\displaystyle x\in \mathrm {Conv} (P)}$ ${\displaystyle x}$ ${\displaystyle r}$ ${\displaystyle P}$

El teorema de Carathéodory simplemente establece que cualquier subconjunto no vacío de tiene el número de Carathéodory . Este límite superior no se alcanza necesariamente. Por ejemplo, la esfera unitaria en tiene el número de Carathéodory igual a 2, ya que cualquier punto dentro de la esfera es la suma convexa de dos puntos en la esfera. ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle \leq d+1}$ ${\displaystyle \mathbb {R} ^{d}}$

Con supuestos adicionales sobre , se pueden obtener límites superiores estrictamente inferiores a los . ^[8] ${\displaystyle P\subset \mathbb {R} ^{d}}$ ${\displaystyle d+1}$

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 colorido de Carathéodory

Sean X ₁ , ..., X _{d +1} conjuntos en R ^d y sea x un punto contenido en la intersección de las envolturas convexas de todos estos d +1 conjuntos.

Entonces existe un conjunto T = { x ₁ , ..., x _{d +1} }, donde x ₁ ∈ X ₁ , ..., x _{d +1} ∈ X _{d +1} , tal que la envoltura convexa de T contiene el punto x . ^[10]

Al considerar los conjuntos X ₁ , ..., 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 símplex arco iris , ya que es un símplex d -dimensional en el que cada esquina tiene un color diferente. ^[12]

Este teorema tiene una variante en la que la envoltura convexa se reemplaza por la envoltura cónica . ^{[10] : Teorema 2.2} Sean X ₁ , ..., X _d conjuntos en R ^d y sea x un punto contenido en la intersección de las envolturas cónicas de todos estos d conjuntos. Entonces existe un conjunto T = { x ₁ , ..., x _d }, donde x ₁ ∈ X ₁ , ..., x _d ∈ X _d , tal que la envoltura cónica de T contiene el punto x . ^[10]

Mustafa y Ray extendieron este colorido teorema desde puntos a cuerpos convexos. ^[12]

El problema computacional de encontrar el conjunto colorido radica en la intersección de las clases de complejidad PPAD y PLS . ^[13]

Véase también

• Lema de Shapley-Folkman
• Teorema de Helly
• Teorema de Kirchberger
• Poliedro N-dimensional
• Teorema de Radon y su generalización Teorema de Tverberg
• Teorema de Kerin-Milman
• Teoría de Choquet

Notas

1. Lovász, László ; Plummer, Doctor en Medicina (1986). Teoría del emparejamiento . Anales de matemáticas discretas. vol. 29. Holanda Septentrional. ISBN 0-444-87916-1.Sr. 0859549  .
2. Danzer, L.; Grünbaum, B .; Klee, V. (1963). "Teorema de Helly y sus parientes". Convexidad . Proc. Symp. Matemáticas puras. Vol. 7. American Mathematical Society . págs. 101–179.Véase en particular la pág. 109.
3. Carathéodory, C. (1911). "Über den Variabilitätsbereich der Fourier'schen Konstanten von positivn harmonischen Funktionen". Rediconti del Circolo Matematico di Palermo (1884-1940) (en alemán). 32 (1): 193–217 [ver página 200 abajo]. doi :10.1007/BF03014795. S2CID  120032616.
4. Steinitz, Ernst (1913). "Bedingt konvergente Reihen und konvexe Systeme". J. Reina Angew. Matemáticas . 1913 (143): 128-175. doi :10.1515/crll.1913.143.128. S2CID  120411668.
5. Leonard, I. Ed; Lewis, JE (2016). "3.3 Envolventes convexos". Geometría de conjuntos convexos . Hoboken, Nueva Jersey: Wiley Blackwell. ISBN 978-1-119-02266-4.
6. Eggleston, HG (1958). Convexidad. Cambridge University Press. doi :10.1017/cbo9780511566172. ISBN 9780511566172.Consulte las páginas 40 y 41.
7. Naszódi, Márton; Polyanskii, Alexandr (2021). "Perron y Frobenius conocen a Carathéodory". La Revista Electrónica de Combinatoria . 28 (3). arXiv : 1901.00540 . doi :10.37236/9996. S2CID  119656227.
8. Bárány, Imre; Karasev, Roman (20 de julio de 2012). "Notas sobre el número de 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.
9. Adiprasito, Karim; Bárány, Imre; Mustafa, Nabil H.; Terpai, Tamás (28-08-2019). "Teoremas de Carathéodory, Helly y Tverberg sin dimensión". arXiv : 1806.08725 [matemáticas.MG].
10. 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.
11. 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.
12. Mustafa, Nabil H.; Ray, Saurabh (6 de abril de 2016). "Una generalización óptima del teorema de Carathéodory de Colorful". Matemáticas discretas . 339 (4): 1300–1305. doi : 10.1016/j.disc.2015.11.019 . ISSN  0012-365X.
13. Meunier, Frédéric; Mulzer, Wolfgang; Sarrabezolles, Pauline; Stein, Yannik (1 de enero de 2017), "El arcoíris al final de la línea: una formulación PPAD del teorema colorido de Carathéodory con aplicaciones", Actas del Simposio anual ACM-SIAM de 2017 sobre algoritmos discretos (SODA) , Actas, Sociedad de Matemáticas Industriales y Aplicadas, págs. 1342–1351, arXiv : 1608.01921 , doi : 10.1137/1.9781611974782.87 , ISBN 978-1-61197-478-2, Número de identificación del sujeto  5784949

Lectura adicional

• Eckhoff, J. (1993). "Teoremas de tipo Helly, Radon y Carathéodory". Manual de geometría convexa . Vol. A, B. Ámsterdam: 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 Sociedad Matemática Americana . 56 (3): 415–511. arXiv : 1706.05975 . doi :10.1090/bull/1653. ISSN  0273-0979. S2CID  32071768.

Enlaces externos

• Enunciado conciso del teorema en términos de envolturas convexas (en PlanetMath )