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:

${\displaystyle 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 ${\displaystyle N\geq {\binom {n}{i}},}$ reemplazamos N con la diferencia, i con i − 1, y repetimos hasta la diferencia termina siendo cero. Definimos

${\displaystyle N^{(i)}={\binom {n_{i}}{i}}+{\binom {n_{i-1}}{i-1}}+\ldots +{\binom {n_{j}}{j}}.}$

Enunciado para complejos simpliciales

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

${\displaystyle 0\leq f_{i}^{(i)}\leq f_{i-1},\quad 1\leq i\leq 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 ${\displaystyle (i-r)}$ elementos dentro de los conjuntos en A. Expandimos N como arriba. Entonces, la cardinalidad de B está acotada inferiormente como sigue:

${\displaystyle |B|\geq {\binom {n_{i}}{i-r}}+{\binom {n_{i-1}}{i-r-1}}+\ldots +{\binom {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 ${\displaystyle (i-r)}$. Si tenemos que U = ${\displaystyle {\binom {x}{i}}}$, entonces ${\displaystyle |B|\geq {\binom {x}{i-r}}}$.

En esta formulación, x no necesariamente es un entero. El valor de la expresión binomial es .${\displaystyle {\binom {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 ${\displaystyle \mathbb {N} }$, el conjunto de los números naturales, dados por ${\displaystyle \{a_{1},a_{2},\ldots ,a_{n}\}}$ con ${\displaystyle a_{1}<a_{2}<\ldots <a_{n}}$ en orden colexicográfico. Por ejemplo, para i = 3, la lista empieza con

${\displaystyle 123,124,134,234,125,135,235,145,245,345,\ldots .}$

Dado un vector ${\displaystyle 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 ${\displaystyle f_{i-1}}$ subconjuntos de tamaño i de ${\displaystyle \mathbb {N} }$ en la lista para ${\displaystyle i=1,\ldots ,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. ${\displaystyle f_{i}\leq f_{i-1}^{(i)},\quad 1\leq i\leq d-1.}$

La implicación más compleja de probar es ${\displaystyle 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 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.

Referencias

• Clements, G. F.; Lindström, B. (1969), «A generalization of a combinatorial theorem of Macaulay», Journal of Combinatorial Theory 7: 230-238, doi:10.1016/S0021-9800(69)80016-5 .. Reprinted in Gessel, Ira; Rota, Gian-Carlo, eds. (1987), Classic Papers in Combinatorics, Boston, Massachusetts: Birkhäuser Boston, Inc., pp. 416-424, ISBN 0-8176-3364-2, doi:10.1007/978-0-8176-4842-8 .
• Harper, L. H. (1966), «Optimal numberings and isoperimetric problems on graphs», Journal of Combinatorial Theory 1: 385-393, doi:10.1016/S0021-9800(66)80059-5 .
• Katona, Gyula O. H. (1968), «A theorem of finite sets», en Erdős, Paul; Katona, Gyula O. H., eds., Theory of Graphs, Akadémiai Kiadó and Academic Press .. Reprinted in Gessel y Rota (1987).
• Knuth, Donald (2011), The Art of Computer Programming, volume 4A: Combinatorial algorithms, part 1, p. 373 ..
• Kruskal, Joseph B. (1963), «The number of simplices in a complex», en Bellman, Richard E., ed., Mathematical Optimization Techniques, University of California Press ..
• Lovász, László (1993), Combinatorial problems and exercises, Amsterdam: North-Holland ..
• Le, Dinh Van; Römer, Tim (2019), A Kruskal–Katona type result and applications .
• Stanley, Richard (1996), Combinatorics and commutative algebra, Progress in Mathematics 41 (2nd edición), Boston, MA: Birkhäuser Boston, Inc., ISBN 0-8176-3836-9 ..
• Schützenberger, M.P. (1959), «A Characteristic Property of Certain Polynomials of E. F. Moore and C. E. Shannon», RLE Quarterly Progress Report 55 (Processing and Transmission of Information): 117-118, consultado el 19 de marzo de 2019 ..

Enlaces externos

• Teorema de Kruskal-Katona en la wiki polymath1.