title: Teorema de Kruskal–Katona
text: # 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.
  
  # Teorema de Kruskal–Katona
  ## Enunciado
  
  Dados dos enteros positivos N e i, hay una manera única de expandir N como suma de coeficientes binomiales como sigue:
      $N={\binom {n_{i}}{i}}+{\binom {n_{i-1}}{i-1}}+\ldots +{\binom {n_{j}}{j}},\quad n_{i}>n_{i-1}>\ldots >n_{j}\geq j\geq 1.$
  Esta expansión puede ser construida aplicando un algoritmo voraz: dejamos que n$_i$ sea el máximo n tal que $N\geq {\binom {n}{i}},$ reemplazamos N con la diferencia, i con i − 1, y repetimos hasta la diferencia termina siendo cero. Definimos
      $N^{(i)}={\binom {n_{i}}{i}}+{\binom {n_{i-1}}{i-1}}+\ldots +{\binom {n_{j}}{j}}.$
  
  # Teorema de Kruskal–Katona
  ## Enunciado
  ### 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\leq f_{i}^{(i)}\leq f_{i-1},\quad 1\leq i\leq d-1.$
  
  # Teorema de Kruskal–Katona
  ## Enunciado
  ### 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|\geq {\binom {n_{i}}{i-r}}+{\binom {n_{i-1}}{i-r-1}}+\ldots +{\binom {n_{j}}{j-r}}.$
  
  # Teorema de Kruskal–Katona
  ## Enunciado
  ### 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 = ${\binom {x}{i}}$, entonces $|B|\geq {\binom {x}{i-r}}$.
  En esta formulación, x no necesariamente es un entero. El valor de la expresión binomial es .${\binom {x}{i}}={\frac {x(x-1)\dots (x-i+1)}{i!}}$
  
  # Teorema de Kruskal–Katona
  ## 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},\ldots ,a_{n}\}$ con $a_{1}<a_{2}<\ldots <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,\ldots .$
  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,\ldots ,d$. Entonces, las siguientes condiciones son equivalentes:
  * El vector f es el f-vector de un complejo simplicial Δ.
  * Δ$_f$ es un complejo simplicial.
  * $f_{i}\leq f_{i-1}^{(i)},\quad 1\leq i\leq d-1.$
  La implicación más compleja de probar es $1\Rightarrow 2$.
  
  # Teorema de Kruskal–Katona
  ## 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 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.
  
  # Teorema de Kruskal–Katona
  ## Ve también
  
  * Teorema de Sperner