Teorema de Kruskal–Katona

En combinatoria algebraica, la teorema de Kruskal–Katona és una caracterisació completa dels f-vectores de complexos abstractes simpliciales. Inclou com a cas especial el teorema de Erdős–Ko–Rado, i ademés pot ser plantejat en térmens d'hipergrafos uniformes. Està nomenat en acabant de que Joseph Kruskal i Gyula O. H. Katona, pero ha segut independentment descobert per varis atres.

Enunciat

Daus dos sancers positivos N i i, hi ha una manera única d'expandir N com sumixca de coeficients binomiales com seguix:

N = (\binom{n_{i}}{i}) + (\binom{n_{i - 1}}{i - 1}) + \dots + (\binom{n_{j}}{j}), n_{i} > n_{i - 1} > \dots > n_{j} \geq j \geq 1.

Esta expansió pot ser construïda aplicant un algoritme voraç: deixem que n_i siga el màxim n tal que $N \geq (\binom{n}{i}),$ reemplacem N en la diferència, i en i − 1, i repetim fins a la diferència termina sent zero. Definim

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

Enunciat per a complexos simpliciales

Un vector integral $(f_{0}, f_{1}, ..., f_{d - 1})$ és el f-vector d'algun complex simplicial $(d - 1)$ -dimensional sí i només si

0 \leq f_{i}^{(i)} \leq f_{i - 1}, 1 \leq i \leq d - 1.

Enunciat per a hipergrafos uniformes

Siga A un conjunt que consta de N subconjunts distints de tamany i de conjunt fix O ("l'univers") i siga B el conjunt de tots els subconjunts en $(i - r)$ elements dins dels conjunts en A. Expandim N com dalt. Llavors, la cardinalidad de B està acotada inferiorment com seguix:

| B | \geq (\binom{n_{i}}{i - r}) + (\binom{n_{i - 1}}{i - r - 1}) + \dots + (\binom{n_{j}}{j - r}) .

Formulació simplificada de Lovász

La següent formulació més dèbil, pero també prou útil i s'atribuïx a László Lovász (1993). Siga A un conjunt de subconjunts de tamany i d'un conjunt fix O ("l'univers"), i siga B el conjunt de tots els subconjunts de A de tamany $(i - r)$ . Si tenim que O = $(\binom{x}{i})$ , llavors $| B | \geq (\binom{x}{i - r})$ .

En esta formulació, x no necessàriament és un sancer. El valor de l'expressió binomial és . $(\binom{x}{i}) = \frac{x (x - 1) \dots (x - i + 1)}{i!}$

Ingredients de la prova

Per a tot sancer positiu i, enlistamos tots els subconjunts de tamany i de $ℕ$ , el conjunt dels número natural, donats per ${a_{1}, a_{2}, \dots, a_{n}}$ en $a_{1} < a_{2} < \dots < a_{n}$ en orde colexicográfico. Per eixemple, per a i = 3, la llista escomença en

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

Donat un vector $f = (f_{0}, f_{1}, ..., f_{d - 1})$ els components del qual són sancers positius, siga Δ_f el subconjunt del conjunt potencia 2^N que consta del conjunt buit, junt en els primers $f_{i - 1}$ subconjunts de tamany i de $ℕ$ en la llista per a $i = 1, \dots, d$ . Llavors, les següents condicions són equivalents:

El vector f és el f-vector d'un complex simplicial Δ.
Δ_f és un complex simplicial.
$f_{i} \leq f_{i - 1}^{(i)}, 1 \leq i \leq d - 1.$

L'implicació més complexa de provar és $1 \Rightarrow 2$ .

Referències

Erro en la seqüencia d'órdens: no existix el mòdul «Citas».. Reprinted in Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
Erro en la seqüencia d'órdens: no existix el mòdul «Citas».

Erro en la seqüencia d'órdens: no existix el mòdul «Citas».. Reprinted in Gessel y Trencada (1987).
Erro en la seqüencia d'órdens: no existix el mòdul «Citas»..
Erro en la seqüencia d'órdens: no existix el mòdul «Citas»..
Erro en la seqüencia d'órdens: no existix el mòdul «Citas»..
Erro en la seqüencia d'órdens: no existix el mòdul «Citas».
Erro en la seqüencia d'órdens: no existix el mòdul «Citas»..
Erro en la seqüencia d'órdens: no existix el mòdul «Citas»..

Este artícul conté una traducció derivada de «Teorema de Kruskal–Katona» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.