Teorema de Kruskal-Katona

Sobre el número de caras de diferentes dimensiones en un complejo simplicial abstracto

En combinatoria algebraica , el teorema de Kruskal-Katona proporciona una caracterización completa de los f -vectores de complejos simpliciales abstractos . Incluye como caso especial el teorema de Erdős-Ko-Rado y puede reformularse en términos de hipergrafos uniformes . Recibe su nombre en honor a Joseph Kruskal y Gyula OH Katona , pero ha sido descubierto independientemente por varios otros.

Declaración

Dados dos números enteros positivos N e i , existe una forma única de expandir N como una suma de coeficientes binomiales de la siguiente manera:

${\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 se puede construir aplicando el algoritmo voraz : establezca n _i como el n máximo tal que reemplace N con la diferencia, i con i − 1, y repita hasta que la diferencia se vuelva cero. Definir ${\displaystyle N\geq {\binom {n}{i}},}$

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

Declaración para complejos simpliciales

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

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

Declaración sobre hipergrafías uniformes

Sea A un conjunto que consta de N subconjuntos distintos de i -elementos de un conjunto fijo U ("el universo") y B el conjunto de todos los subconjuntos de i-elementos de los conjuntos en A. Desarrolle N como se indica arriba. Entonces la cardinalidad de B está acotada por debajo de la siguiente manera: ${\displaystyle (i-r)}$

${\displaystyle |B|\geq {\binom {n_{i}}{i-r}}+{\binom {n_{i-1}}{i-r-1}}+\ldots +{\binom {n_{j}}{j-r}}.}$

La formulación simplificada de Lovász

La siguiente forma más débil pero útil se debe a László Lovász  (1993, 13.31b). Sea A un conjunto de subconjuntos de i elementos de un conjunto fijo U ("el universo") y B el conjunto de todos los subconjuntos de elementos de los conjuntos en A . Si entonces . ${\displaystyle (i-r)}$ ${\displaystyle |A|={\binom {x}{i}}}$ ${\displaystyle |B|\geq {\binom {x}{i-r}}}$

En esta formulación, x no tiene por qué ser un número 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 cada i positivo , enumerar todos los subconjuntos de elementos i a ₁ < a ₂ < … a _i del conjunto N de números naturales en el orden colexicográfico . Por ejemplo, para i = 3, la lista comienza

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

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

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

La implicación difícil es 1 ⇒ 2.

Historia

El teorema recibe su nombre de Joseph Kruskal y Gyula OH Katona , quienes lo publicaron en 1963 y 1968 respectivamente. Según Le & Römer (2019), fue descubierto independientemente por Kruskal (1963), Katona (1968), Marcel-Paul Schützenberger  (1959), Harper (1966) y Clements & Lindström (1969). Donald Knuth  (2011) escribe que la primera de estas referencias, de Schützenberger, tiene una prueba incompleta.

Véase también

• Teorema de Sperner

Referencias

• Clements, GF; Lindström, B. (1969), "Una generalización de un teorema combinatorio de Macaulay", Journal of Combinatorial Theory , 7 : 230–238, doi : 10.1016/S0021-9800(69)80016-5 , MR  0246781. Reimpreso en Gessel, Ira ; Rota, Gian-Carlo , eds. (1987), Classic Papers in Combinatorics , Boston, Massachusetts: Birkhäuser Boston, Inc., págs. 416–424, doi :10.1007/978-0-8176-4842-8, ISBN 0-8176-3364-2, Sr.  0904286
• Harper, LH (1966), "Numeraciones óptimas y problemas isoperimétricos en grafos", Journal of Combinatorial Theory , 1 : 385–393, doi : 10.1016/S0021-9800(66)80059-5 , MR  0200192
• Katona, Gyula OH (1968), "Un teorema de conjuntos finitos", en Erdős, Paul ; Katona, Gyula OH (eds.), Teoría de grafos , Akadémiai Kiadó y Academic Press. Reimpreso en Gessel & Rota (1987, págs. 381–401).
• Knuth, Donald (2011), "7.2.1.3", El arte de la programación informática, volumen 4A: Algoritmos combinatorios, parte 1 , pág. 373.
• Kruskal, Joseph B. (1963), "El número de símplices en un complejo", en Bellman, Richard E. (ed.), Técnicas de optimización matemática , University of California Press.
• Lovász, László (1993), Problemas y ejercicios combinatorios , Ámsterdam: Holanda Septentrional, ISBN 9780444815040.
• Le, Dinh Van; Römer, Tim (2019), Un resultado y aplicaciones de tipo Kruskal-Katona , arXiv : 1903.02998
• Stanley, Richard (1996), Combinatoria y álgebra conmutativa , Progress in Mathematics, vol. 41 (2.ª ed.), Boston, MA: Birkhäuser Boston, Inc., ISBN 0-8176-3836-9.
• Schützenberger, MP (1959), "Una propiedad característica de ciertos polinomios de EF Moore y CE Shannon", RLE Quarterly Progress Report , 55 (Procesamiento y transmisión de información): 117–118 , consultado el 19 de marzo de 2019.

Enlaces externos

• Teorema de Kruskal-Katona en la wiki de Polymath1