Helly para conjuntos finitos

Cuando empecé a escribir este blog mencioné el teorema de Helly, lo que dice es lo siguiente

Teorema 1 (Helly 1924): Sea una familia finita de conjuntos convexos en .  Si cada de ellos tienen un punto en común, todos los conjuntos de tienen un punto en común.

Si uno quita la condición de que los conjuntos sean convexos el teorema se vuelve claramente falso.  La idea general detrás de este teorema es la siguiente.

Dada una familia de conjuntos que satisfacen cierta propiedad , propiedades «locales» sobre sus intersecciones tienen consecuencias globales sobre sus intersecciones.  El teorema de Helly es el ejemplo clásico, dónde es «ser conjuntos convexos».  Los teoremas de intersecciones de convexos no son el único lugar donde este tipo de teoremas aparece.  Por ejemplo, si en vez de convexidad le pedimos a los conjuntos que ciertos grupos de homología sean triviales, el teorem se mantiene [1].  Si queremos relajar un poco la condición del teorema, ya no obtenemos una intersección de todos los conjuntos.   Sin embargo, sigue siendo interesante (y usualmente muy difícil) poder demostrar que con pocos puntos podemos interesectar a toda la familia .

Lo que quería presentar en esta entrada es una versión de este teorema pero fuera de un sentido geométrico.  Así como en la condición que funciona para conjuntos finitos es que todos tengan la misma cantidad de elementos.  El teorema es el siguiente:

Teorema 2 (Bollobás 1965):  Sea una familia finita de conjuntos de tamaño .  Si para cada de ellos existe un conjunto de tamaño que los intersecta a todos, entonces existe un conjunto de de tamaño que intersecta a todo .

Para ver que el número es óptimo, basta considerar como todos los subconjuntos de tamaño de un conjunto de elementos.  No es posible intersectar todos con un conjunto de tamaño , pero sí es posible hacerlo para cualesquiera .

Si el teorema no fuera cierto, podemos ir quitando conjuntos de hasta que sin importar cuál conjunto quitemos, podamos encontrar dicho conjunto .  Supongamos que en este momento los elementos de que quedan son .  Sabemos que al quitar cualquier podermos encontrar un conjunto de tamaño que intersecta a todos los otros .  Como todo no podía ser intersectada con un conjunto de tamaño , tenemos que y son disjuntos.  Además, sabemos que .  Con esto, basta demostrar lo siguiente:

Teorema 3 (Bollobás 1965).  Sean conjuntos de tamaño y conjuntos de tamaño tales que si y solo si .  Entonces .

La siguiente demostración es de Lovász y hace uso del álgebra exterior (cosa que es sorprendente si consideramos que el problema es completamente combinatorio).

Demostración: Sea la unión de todos los y .  Sin pérdida de generalidad podemos considerar que es un subconjunto de de tal forma que cualesquiera puntos de son linealmente independientes.  Dado  definimos el producto exterior de sus elementos.  Vamos a demostrar que son linealmente independientes.  Para eso consideremos una combinación lineal de ellos que dé , es decir

Si consideramos el producto exterior con tenemos que es el producto exterior de todos los elementos de y .  Si , hay al menos un elemento repetido en este producto exterior, por lo que da .  Esto implica que

.  Como es un conjunto linealmente independiente, el producto exterior de sus elementos no es , por lo que .  Con esto tenemos que todos los coeficientes son , por lo que los son linealmente independientes.

Sin embargo, cada uno de ellos es el producto exterior de elementos de , por lo que están en un espacio vectorial de dimensión .  Con esto, no puede haber más de  $latex {{r+s}\choose{s}}$ de ellos, como se quería probar.

[1] Debrunner, H. (1970). Helly type theorems derived from basic singular homology. The American Mathematical Monthly, 77(4), 375–380.