Transversales geométricas y más allá del Teorema de Helly Coloreado

Autor: Leonardo Ignacio Martínez Sandoval
Coautor(es): Edgardo Roldán Pensado, Natan Rubin
El teorema de Helly Coloreado es una de las generalizaciones más sorprendentes y anti-intuirivas del teorema de Helly. Para enunciarlo, comenzamos con una famila F de conjuntos convexos en R^d partida en la unión (no necesariamente disjunta) F=F_1 U ... U F_{d+1}. Pensamos a cada una de las F_i como una clase cromática. Decimos que esta familia satisface la hipótesis colorida si cada subfamilia colorida de tamaño d+1 (que consiste de un conjunto de cada color) tiene intersección no vacía. El resultado clásico dice que si F satisface la hipótesis colorida, entonces al menos una clase cromática tiene intersección no vacía. De aquí surge una pregunta natural: ¿Por qué la conclusión habla únicamente de una clase cromática? ¿Qué podemos decir del resto? Un ejemplo sencillo muestra que puede que no haya otra clase colorida con intersección no vacía. Lo que nosotros probamos es que, sin embargo, siempre se da una dicotomía. O bien existe una clase colorida que puede ser pinchada con pocos puntos, o bien todas las clases cromáticas (es decir, toda la familia F) pueden ser pinchadas con pocas lineas. Aquí "pocos" es un número que depende únicamente de d (y no de |F|). El resultado es sorprendente en vista de la escasez de resultados para lineas transversales en dimensión mayor a dos. En más generalidad, damos una clasificación de las familias que satisfacen la hipótesis colorida en términos de su estructura de transversales por flats. La prueba está basada en el esquema de Alon-Kleitman para probar el Teorema (p,q). Este enfoque combina la existencia de epsilon-nets pequeñas, la dualidad de programación lineal y el teorema de Helly fraccional. En la literatura no hay resultados de epsilon-nets de lineas para familias generales de convexos, ni resultados de Helly fraccionales para lineas transversales. Sin embargo, un ingenioso enfoque por inducción nos permite usar repetidamente resultados de epsilon-nets de planos para acotar números transversales que aparecen de manera natural en el problema. De aquí, continuamos con trucos similares a los que Alon y Kleitman usan en su demostración.