Teorema de Kruskal–Katona

En combinatoria algebraica, el teorema de Kruskal–Katona es una caracterización completa de los f-vectores de complejos abstractos simpliciales. Incluye como caso especial el teorema de Erdős–Ko–Rado, y además puede ser planteado en términos de hipergrafos uniformes. Está nombrado después de que Joseph Kruskal y Gyula O. H. Katona, pero ha sido independientemente descubierto por varios otros.

Enunciado

Dados dos enteros positivos N e i, hay una manera única de expandir N como suma de coeficientes binomiales como sigue:

$N=(\genfrac{}{}{0ex}{}{n_i}{i})+(\genfrac{}{}{0ex}{}{n_{i-1}}{i-1})+\dots +(\genfrac{}{}{0ex}{}{n_j}{j}),n_i>n_{i-1}>\dots >n_j\ge j\ge 1.$

Esta expansión puede ser construida aplicando un algoritmo voraz: dejamos que n_i sea el máximo n tal que $N\ge (\genfrac{}{}{0ex}{}{n}{i}),$ reemplazamos N con la diferencia, i con i − 1, y repetimos hasta la diferencia termina siendo cero. Definimos

$N^{(i)}=(\genfrac{}{}{0ex}{}{n_i}{i})+(\genfrac{}{}{0ex}{}{n_{i-1}}{i-1})+\dots +(\genfrac{}{}{0ex}{}{n_j}{j}).$

Enunciado para complejos simpliciales

Un vector integral $(f_0,f_1,...,f_{d-1})$ es el f-vector de algún complejo simplicial $(d-1)$-dimensional sí y sólo si

$0\le f_i^{(i)}\le f_{i-1},1\le i\le d-1.$

Enunciado para hipergrafos uniformes

Sea A un conjunto que consta de N subconjuntos distintos de tamaño i de conjunto fijo U ("el universo") y sea B el conjunto de todos los subconjuntos con $(i-r)$ elementos dentro de los conjuntos en A. Expandimos N como arriba. Entonces, la cardinalidad de B está acotada inferiormente como sigue:

$|B|\ge (\genfrac{}{}{0ex}{}{n_i}{i-r})+(\genfrac{}{}{0ex}{}{n_{i-1}}{i-r-1})+\dots +(\genfrac{}{}{0ex}{}{n_j}{j-r}).$

Formulación simplificada de Lovász

La siguiente formulación más débil, pero también bastante útil y se atribuye a László Lovász (1993). Sea A un conjunto de subconjuntos de tamaño i de un conjunto fijo U ("el universo"), y sea B el conjunto de todos los subconjuntos de A de tamaño $(i-r)$. Si tenemos que U = $(\genfrac{}{}{0ex}{}{x}{i})$, entonces $|B|\ge (\genfrac{}{}{0ex}{}{x}{i-r})$.

En esta formulación, x no necesariamente es un entero. El valor de la expresión binomial es .$(\genfrac{}{}{0ex}{}{x}{i})=\frac{x(x-1)\dots (x-i+1)}{i!}$

Ingredientes de la prueba

Para todo entero positivo i, enlistamos todos los subconjuntos de tamaño i de $\mathbb{N}$, el conjunto de los números naturales, dados por $\{a_1,a_2,\dots ,a_n\}$ con $a_1<a_2<\dots <a_n$ en orden colexicográfico. Por ejemplo, para i = 3, la lista empieza con

$123,124,134,234,125,135,235,145,245,345,\dots .$

Dado un vector $f=(f_0,f_1,...,f_{d-1})$ cuyos componentes son enteros positivos, sea Δ_f el subconjunto del conjunto potencia 2^N que consta del conjunto vacío, junto con los primeros $f_{i-1}$ subconjuntos de tamaño i de $\mathbb{N}$ en la lista para $i=1,\dots ,d$. Entonces, las siguientes condiciones son equivalentes:

1. El vector f es el f-vector de un complejo simplicial Δ.
2. Δ_f es un complejo simplicial.
3. $f_i\le f_{i-1}^{(i)},1\le i\le d-1.$

La implicación más compleja de probar es $1\Rightarrow 2$.

Historia

El teorema está nombrado después de que Joseph Kruskal y Gyula O. H. Katona, quienes publicaron su resultado en los años 1963 y 1968, respectivamente. Según Plantilla:Harvtxt, fue descubierto independientemente por Kruskal (1963), Katona (1968), Marcel-Paul Schützenberger (1959), Harper (1966), y Plantilla:Harvtxt. Donald Knuth (2011) escribe que la más temprana de estas referencias, por Schützenberger, tiene una prueba incompleta.

Referencias

• Plantilla:Obra citada. Reprinted in Plantilla:Obra citada
• Plantilla:Obra citada
• Plantilla:Obra citada. Reprinted in Plantilla:Harvtxt.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada.
• Plantilla:Obra citada
• Plantilla:Obra citada.
• Plantilla:Obra citada.

Enlaces externos

• Teorema de Kruskal-Katona en la wiki polymath1.