El teorema de Helly es un resultado básico en geometría discreta en la intersección de conjuntos convexos . Fue descubierto por Eduard Helly en 1913, [1] pero no lo publicó hasta 1923, momento en el que ya habían aparecido pruebas alternativas de Radon (1921) y König (1922) . El teorema de Helly dio lugar a la noción de familia Helly .
Declaración
Sea X 1 , ..., X n una colección finita de subconjuntos convexos de R d , con n > d + 1 . Si la intersección de cada d + 1 de estos conjuntos no está vacía, entonces toda la colección tiene una intersección no vacía; es decir,
Para colecciones infinitas hay que asumir compacidad:
Sea { X α } una colección de subconjuntos convexos compactos de R d , de modo que cada subcolección de cardinalidad como máximo d + 1 tiene una intersección no vacía. Entonces toda la colección tiene una intersección no vacía.
Prueba
Demostramos la versión finita, usando el teorema de Radon como en la demostración de Radon (1921) . La versión infinita sigue entonces por la caracterización de la propiedad de la intersección finita de la compacidad : una colección de subconjuntos cerrados de un espacio compacto tiene una intersección no vacía si y solo si cada subcolección finita tiene una intersección no vacía (una vez que fija un solo conjunto, la intersección de todos los demás con él son subconjuntos cerrados de un espacio compacto fijo).
La prueba es por inducción :
Caso base: Sea n = d + 2 . Según nuestros supuestos, para todo j = 1, ..., n hay un punto x j que está en la intersección común de todo X i con la posible excepción de X j . Ahora aplicamos el teorema de Radon al conjunto A = { x 1 , ..., x n }, que nos proporciona subconjuntos disjuntos A 1 , A 2 de A tales que el casco convexo de A 1 interseca el casco convexo de A 2 . Suponga que p es un punto en la intersección de estos dos cascos convexos. Afirmamos que
De hecho, considere cualquier j ∈ {1, ..., n }. Demostraremos que p ∈ X j . Tenga en cuenta que el único elemento de A que puede no estar en X j es x j . Si x j ∈ A 1 , entonces x j ∉ A 2 , y por lo tanto X j ⊃ A 2 . Dado que X j es convexo, también contiene el casco convexo de A 2 y, por lo tanto, también p ∈ X j . Asimismo, si x j ∉ A 1 , entonces X j ⊃ A 1 , y por el mismo razonamiento p ∈ X j . Dado que p está en todo X j , también debe estar en la intersección.
Arriba, hemos asumido que los puntos x 1 , ..., x n son todos distintos. Si este no es el caso, digamos que x i = x k para algún i ≠ k , entonces x i está en cada uno de los conjuntos X j , y nuevamente llegamos a la conclusión de que la intersección no está vacía. Esto completa la demostración en el caso n = d + 2 .
Paso inductivo: suponga que n > d + 2 y que el enunciado es verdadero para n −1 . El argumento anterior muestra que cualquier subcolección de d + 2 conjuntos tendrá una intersección no vacía. Entonces podemos considerar la colección donde reemplazamos los dos conjuntos X n −1 y X n con el conjunto único X n −1 ∩ X n . En esta nueva colección, cada subcolección de d + 1 conjuntos tendrá una intersección no vacía. Por lo tanto, se aplica la hipótesis inductiva y muestra que esta nueva colección tiene una intersección no vacía. Esto implica lo mismo para la colección original y completa la prueba.
Teorema de Helly colorido
El colorido teorema de Helly es una extensión del teorema de Helly en el que, en lugar de una colección, hay d +1 colecciones de subconjuntos convexos de R d .
Si, para cada elección de una transversal , un conjunto de cada colección, hay un punto en común para todos los conjuntos elegidos, entonces para al menos una de las colecciones, hay un punto en común para todos los conjuntos de la colección.
En sentido figurado, se puede considerar que las colecciones d +1 son de d +1 colores diferentes. Entonces el teorema dice que, si cada elección de un conjunto por color tiene una intersección no vacía, entonces existe un color tal que todos los conjuntos de ese color tienen una intersección no vacía. [2]
Teorema de Helly fraccional
Para cada a > 0 hay algo de b > 0 tal que, si X 1 , ..., X n son n subconjuntos convexos de R d , y al menos una a -fracción de ( d +1) -tuplas de los conjuntos tienen un punto en común, entonces una fracción de al menos b de los conjuntos tienen un punto en común. [2]
Ver también
Notas
- ^ Danzer, Grünbaum y Klee (1963) .
- ^ a b Kalai, Gil (15 de marzo de 2019), "Noticias sobre Helly fraccional, Helly colorido y radón" , Combinatoria y más , consultado el 13 de julio de 2020
Referencias
- Bollobás, B. (2006), "Problema 29, Conjuntos convexos de intersección: Teorema de Helly", El arte de las matemáticas: La hora del café en Memphis , Cambridge University Press, págs. 90–91, ISBN 0-521-69395-0.
- Danzer, L .; Grünbaum, B .; Klee, V. (1963), "Teorema de Helly y sus parientes", Convexidad , Proc. Symp. Pure Math., 7 , American Mathematical Society , págs. 101–180.
- Eckhoff, J. (1993), "Teoremas de tipo Helly, Radon y Carathéodory", Handbook of Convex Geometry , A, B , Amsterdam: North-Holland, págs. 389–448.
- Heinrich Guggenheimer (1977) Geometría aplicable , página 137, Krieger, Huntington ISBN 0-88275-368-1 .
- Helly, E. (1923), "Über Mengen konvexer Körper mit gemeinschaftlichen Punkten", Jahresbericht der Deutschen Mathematiker-Vereinigung , 32 : 175-176.
- König, D. (1922), "Über konvexe Körper", Mathematische Zeitschrift , 14 (1): 208–220, doi : 10.1007 / BF01215899.
- Radon, J. (1921), "Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten", Mathematische Annalen , 83 (1–2): 113–115, doi : 10.1007 / BF01464231.