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.
Dados dos enteros positivos N e i, hay una manera única de expandir N como suma de coeficientes binomiales como sigue: Esta expansión puede ser construida aplicando un algoritmo voraz: dejamos que ni sea el máximo n tal que
reemplazamos N con la diferencia, i con i − 1, y repetimos hasta la diferencia termina siendo cero.
Definimos Un vector integral
es el f-vector de algún complejo simplicial
-dimensional sí y sólo si 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
elementos dentro de los conjuntos en A. Expandimos N como arriba.
Entonces, la cardinalidad de B está acotada inferiormente como sigue: 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
Si tenemos que U =
En esta formulación, x no necesariamente es un entero.
El valor de la expresión binomial es .
Para todo entero positivo i, enlistamos todos los subconjuntos de tamaño i de
, el conjunto de los números naturales, dados por
Por ejemplo, para i = 3, la lista empieza con Dado un vector
cuyos componentes son enteros positivos, sea Δf el subconjunto del conjunto potencia 2N que consta del conjunto vacío, junto con los primeros
Entonces, las siguientes condiciones son equivalentes: La implicación más compleja de probar es
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 Le y Römer (2019), fue descubierto independientemente por Kruskal (1963), Katona (1968), Marcel-Paul Schützenberger (1959), Harper (1966), y Clements y Lindström (1969).
Donald Knuth (2011) escribe que la más temprana de estas referencias, por Schützenberger, tiene una prueba incompleta.