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, cuando 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 .
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; eso es,
Para colecciones infinitas hay que asumir compacidad:
Sea { X α } una colección de subconjuntos compactos convexos de R d , tal que cada subcolección de cardinalidad como máximo d + 1 tenga 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 luego sigue la caracterización de la propiedad de 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 se fija un conjunto único, 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 Radón al conjunto A = { x 1 , ..., x n }, que nos proporciona subconjuntos disjuntos A 1 , A 2 de A tales que la cubierta convexa de A 1 intersecta la cubierta convexa de A 2 . Supongamos que p es un punto en la intersección de estos dos cascos convexos. Afirmamos que
De hecho, considere cualquier j ∈ {1, ..., n }. Probaremos 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 tanto X j ⊃ A 2 . Dado que X j es convexo, también contiene la cáscara convexa 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 . Como p está en cada 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 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 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 conjuntos d + 1 tendrá una intersección no vacía. Por 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 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]
Para cada a > 0 hay algún b > 0 tal que, si X 1 , ..., X n son n subconjuntos convexos de R d , y al menos una fracción a de ( d +1 ) tuplas de los conjuntos tienen un punto en común, entonces una fracción de al menos b de los conjuntos tiene un punto en común. [2]
