Teorema de Helly

El teorema de Helly es un resultado fundamental en geometría discreta sobre la intersección de elementos convexos. Fue descubierto por Eduard Helly en 1913, pero no lo publicó hasta 1923. Para entonces, 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.

Enunciado

Sea X₁, ..., X_n una colección finita de subconjuntos convexos de ${\displaystyle \mathbb {R} ^{d}}$, con ${\displaystyle n\geq d+1}$. Si la intersección de cada ${\displaystyle d+1}$ de estos conjuntos no es vacía, entonces la colección completa tiene una intersección no vacía; es decir,

${\displaystyle \bigcap _{j=1}^{n}X_{j}\neq \varnothing .}$

Para colecciones infinitas, es necesario suponer compacidad:

Sea ${\displaystyle \{X_{\alpha }\}}$ una familia de subconjuntos convexos compactos de ${\displaystyle \mathbb {R} ^{d}}$, tal que toda subfamilia de cardinalidad a lo sumo ${\displaystyle d+1}$ tiene intersección no vacía. Entonces, la familia completa tiene intersección no vacía.

Demostración

Se demuestra la versión finita utilizando el lema de Radon, tal como en la demostración de Radon (1921). La versión infinita se deduce entonces de la caracterización de la compacidad mediante la propiedad de la intersección finita: una colección de subconjuntos cerrados de un espacio compacto tiene una intersección no vacía si y solo si toda subcolección finita tiene una intersección no vacía (una vez fijado un conjunto, la intersección de todos los demás con él son subconjuntos cerrados de un espacio compacto fijo).

La demostración se realiza mediante inducción:

Caso base: Sea n = d + 2. Según las hipótesis fijadas, para cada j = 1, ..., n existe un punto x_j que pertenece a la intersección común de todos los X_i, con la posible excepción de X_j. Ahora se aplica el lema de Radon al conjunto A = {x₁, ..., x_n}, lo que proporciona subconjuntos disjuntos A₁, A₂ de A tales que la envolvente convexa de A₁ interseca la envolvente convexa de A₂. Supóngase que p es un punto en la intersección de estas dos envolventes convexas. Se puede afirmar que

${\displaystyle p\in \bigcap _{j=1}^{n}X_{j}.}$

En efecto, considérse cualquier j ∈ {1, ..., n}.. Se demuestra que p ∈ X_j.. Nótese que el único elemento de A que podría no estar en X_j es x_j. Si x_j ∈ A₁, entonces x_j ∉ A₂ y, por tanto, X_j ⊃ A₂. Dado que X_j es convexo, contiene también la envolvente convexa de A₂ y, en consecuencia, también p ∈ X_j. Del mismo modo, si x_j ∉ A₁, entonces X_j ⊃ A₁ y, siguiendo el mismo razonamiento, p ∈ X_j. Puesto que p está en cada X_j, debe estar también en la intersección.

Más arriba se ha supuesto que los puntos x₁, ..., x_n son todos distintos. Si este no fuera el caso —por ejemplo, si x_i = x_k para algún i ≠ k—, entonces x_i estaría en cada uno de los conjuntos X_j y, de nuevo, se concluiría que la intersección no es vacía. Esto completa la demostración para el caso n = d + 2.

Paso inductivo: Supóngase que n > d + 2 y que la afirmación es cierta para n−1. El argumento anterior demuestra que cualquier subcolección de conjuntos d + 2 tendrá una intersección no vacía. Se puede considerar entonces la colección en la que se sustituyen los dos conjuntos X_n−1 y X_n por el único conjunto X_n−1 ∩ X_n. En esta nueva colección, cualquier subcolección de conjuntos d + 1 tendrá una intersección no vacía. Por tanto, se aplica la hipótesis de inducción, demostrando que esta nueva colección tiene una intersección no vacía. Esto implica lo mismo para la colección original y completa la demostración.

Demostración topológica del caso base

Sea ${\displaystyle X=X_{1}\cup \cdots \cup X_{n+2}}$ y considérese el recubrimiento ${\displaystyle {\mathcal {U}}=\{X_{i}\}_{i=1}^{n+2}}$. Dado que la intersección de conjuntos convexos es convexa, toda intersección finita no vacía de elementos de ${\displaystyle {\mathcal {U}}}$ es contráctil. Por consiguiente, ${\displaystyle {\mathcal {U}}}$ es un buen recubrimiento.

Según el resultado básico del lema del nervio, ${\displaystyle X}$ es homotópicamente equivalente a la realización geométrica ${\displaystyle |{\mathcal {N}}|}$ del nervio ${\displaystyle {\mathcal {N}}}$ del recubrimiento. Suponiendo que

${\displaystyle X_{1}\cap \cdots \cap X_{n+2}=\varnothing ,}$

el nervio ${\displaystyle {\mathcal {N}}}$ es el complejo de frontera del símplice ${\displaystyle \Delta ^{n+1}}$ formado por todas las caras ${\displaystyle n}$. Por tanto, ${\displaystyle |{\mathcal {N}}|}$ es homeomorfo a ${\displaystyle S^{n}}$. De ello se deduce que

${\displaystyle H_{n}(X)\cong H_{n}(S^{n})\cong \mathbb {Z} .}$

Esto supone una contradicción, ya que ${\displaystyle X}$ es una variedad de dimensión ${\displaystyle n}$ no compacta, y el grupo de homología superior de una variedad no compacta es nulo.

Teorema de Helly colorido

El teorema de Helly colorido es una extensión del teorema de Helly en la que, en lugar de una sola 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— existe un punto común a todos los conjuntos elegidos, entonces para al menos una de las colecciones existe un punto común a todos los conjuntos de dicha colección.

En sentido figurado, se puede considerar que las d+1 colecciones corresponden a d+1 colores diferentes. Entonces, el teorema afirma que si toda elección de un conjunto por color tiene una intersección no vacía, existe un color tal que todos los conjuntos de ese color tienen una intersección no vacía.

Teorema de Helly fraccionario

Para todo a > 0 existe un b > 0 tal que, si X₁, ..., X_n son n subconjuntos convexos de R^d y al menos una fracción a de las tuplas de d+1 conjuntos tiene un punto en común, entonces una fracción de al menos b de los conjuntos tiene un punto en común.

Véase también

• Teorema de Carathéodory
• Teorema de Doignon
• Teorema de Kirchberger
• Lema de Shapley–Folkman
• Teorema de Krein-Milman
• Teoría de Choquet
• Lema de Radon, y su generalización, Tverberg's theorem
• Teorema de la intersección de Cantor - otro teorema sobre la intersección de conjuntos
• Familia de Helly

Referencias

Bibliografía

• Bollobás, B. (2006), «Problem 29, Intersecting Convex Sets: Helly's Theorem», The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, pp. 90-91, ISBN 0-521-69395-0 ..
• Danzer, L.; Grünbaum, B.; Klee, V. (1963), «Helly's theorem and its relatives», Convexity, Proc. Symp. Pure Math. 7, American Mathematical Society, pp. 101-180 ..
• Eckhoff, J. (1993), «Helly, Radon, and Carathéodory type theorems», Handbook of Convex Geometry, A, B, Amsterdam: North-Holland, pp. 389-448 ..
• Heinrich Guggenheimer (1977) Applicable Geometry, 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, S2CID 128041360, doi:10.1007/BF01215899 ..
• Radon, J. (1921), «Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten», Mathematische Annalen 83 (1–2): 113-115, S2CID 121627696, doi:10.1007/BF01464231 ..