En combinatoria algebraica , el teorema de Kruskal-Katona da 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 hipergráficos uniformes . Lleva el nombre de Joseph Kruskal y Gyula OH Katona , pero ha sido descubierto de forma independiente por varios otros.
Declaración
Dados dos enteros positivos N e i , existe una forma única de expandir N como una suma de coeficientes binomiales de la siguiente manera:
Esta expansión se puede construir aplicando el algoritmo codicioso : establezca n i para que sea el máximo n tal quereemplace N con la diferencia, i con i - 1, y repita hasta que la diferencia sea cero. Definir
Declaración para complejos simpliciales
Un vector integral es el vector f de algunos-complejo simplicial dimensional si y solo si
Declaración para hipergráficos uniformes
Deje que A sea un conjunto que consiste en N distinta i subconjuntos -elemento de un conjunto fijo T ( "el universo") y B es el conjunto de todossubconjuntos -elemento de los sistemas en A . Expanda N como se indicó anteriormente. Entonces, la cardinalidad de B se limita a continuación de la siguiente manera:
Formulación simplificada de Lovász
La siguiente forma más débil pero útil se debe a László Lovász ( 1993 ) Sea A un conjunto de subconjuntos de elementos i de un conjunto fijo U ("el universo") y B el conjunto de todossubconjuntos -elemento de los sistemas en A . Si luego .
En esta formulación, no es necesario que x sea un número entero. El valor de la expresión binomial es.
Ingredientes de la prueba
Para cada i positivo , enumere todos los subconjuntos de elementos i a 1 < a 2 <… a i del conjunto N de números naturales en el orden colexicográfico . Por ejemplo, para i = 3, la lista comienza
Dado un vector con componentes enteros positivos, sea Δ f el subconjunto del conjunto de potencia 2 N que consiste en el conjunto vacío junto con el primero i -subconjuntos de elementos de N en la lista para i = 1,…, d . Entonces las siguientes condiciones son equivalentes:
- Vector f es el f -vector de un complejo simplicial Δ .
- Δ f es un complejo simplicial.
La implicación difícil es 1 ⇒ 2.
Historia
El teorema lleva el nombre de Joseph Kruskal y Gyula OH Katona , quienes lo publicaron en 1963 y 1968 respectivamente. Según Le & Römer (2019) , fue descubierto de forma independiente 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.
Ver también
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), Documentos clásicos en combinatoria , Boston, Massachusetts: Birkhäuser Boston, Inc., págs. 416–424, doi : 10.1007 / 978-0-8176-4842-8 , ISBN 0-8176-3364-2, MR 0904286
- Harper, LH (1966), "Numeraciones óptimas y problemas isoperimétricos en gráficos", 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 los gráficos , Akadémiai Kiadó y Academic Press. Reimpreso en Gessel y 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. 373.
- Kruskal, Joseph B. (1963), "El número de simples en un complejo", en Bellman, Richard E. (ed.), Mathematical Optimization Techniques , University of California Press.
- Lovász, László (1993), Problemas y ejercicios combinatorios , Amsterdam: North-Holland.
- Le, Dinh Van; Römer, Tim (2019), A Kruskal – Katona type result and applications , arXiv : 1903.02998
- Stanley, Richard (1996), Combinatoria y álgebra conmutativa , Progreso en matemáticas, 41 (2a ed.), Boston, MA: Birkhäuser Boston, Inc., ISBN 0-8176-3836-9.
- Schützenberger, MP (1959), "A Characteristic Property of Certain Polynomials of EF Moore and CE 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 el wiki de polymath1