El teorema de Helly es un resultado básico en geometría discreta sobre la intersección de conjuntos convexos . Fue descubierto por Eduard Helly en 1913, [1] pero no publicado por él hasta 1923, momento en el que ya habían aparecido demostraciones alternativas de Radon (1921) y König (1922). El teorema de Helly dio lugar a la noción de familia de Helly .
Sea X 1 , ..., X n una colección finita de subconjuntos convexos de , con . Si la intersección de cada uno 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 una colección de subconjuntos convexos compactos de , tales que cada subcolección de cardinalidad tiene como máximo una intersección no vacía. Entonces toda la colección tiene una intersección no vacía.
Demostramos la versión finita, utilizando el teorema de Radon como en la demostración de Radon (1921). La versión infinita se deduce entonces de la propiedad de intersección finita que caracteriza la compacidad : una colección de subconjuntos cerrados de un espacio compacto tiene una intersección no vacía si y sólo si cada subcolección finita tiene una intersección no vacía (una vez que se fija un único 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 nuestras suposiciones, para cada j = 1, ..., n hay un punto x j que está en la intersección común de todos los X i con la posible excepción de X j . Ahora aplicamos el teorema de Radon al conjunto A = { x 1 , ..., x n }, lo que nos proporciona subconjuntos disjuntos A 1 , A 2 de A tales que la envoltura convexa de A 1 interseca la envoltura convexa de A 2 . Supongamos que p es un punto en la intersección de estas dos envolturas convexas. Afirmamos que
De hecho, considere cualquier j ∈ {1, ..., n }. Probaremos que p ∈ X j . Nótese 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 . Como X j es convexo, entonces también contiene la envoltura convexa de A 2 y por lo tanto también p ∈ X j . Del mismo modo, si x j ∉ A 1 , entonces X j ⊃ A 1 , y por el mismo razonamiento p ∈ X j . Como p está en cada X j , también debe estar en la intersección.
Arriba, hemos supuesto que los puntos x 1 , ..., x n son todos distintos. Si este no es el caso, digamos x i = x k para algún i ≠ k , entonces x i está en cada uno de los conjuntos X j , y nuevamente concluimos que la intersección no está vacía. Esto completa la prueba en el caso n = d + 2 .
Paso inductivo: supongamos que n > d + 2 y que la afirmación es verdadera para n −1 . El argumento anterior muestra que cualquier subcolección de d + 2 conjuntos tendrá una intersección no vacía. Podemos entonces considerar la colección donde reemplazamos los dos conjuntos X n −1 y X n con el único conjunto 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.
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 a todos los conjuntos elegidos, entonces, para al menos una de las colecciones, hay un punto en común a todos los conjuntos de la colección.
En sentido figurado, se puede considerar que las d +1 colecciones tienen 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]
Para cada a > 0 existe algún 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]
