En combinatoire algébrique, le théorème de Kruskal-Katona, nommé d'après Joseph Kruskal et Gyula O. H. Katona, caractérise les f-vecteurs de complexes simpliciaux abstraits. Il généralise le théorème d'Erdős-Ko-Rado et peut, comme lui, être reformulé en termes d'hypergraphes uniformes. Il a été démontré indépendamment par Marcel-Paul Schützenberger, mais cette contribution est passée inaperçue pendant plusieurs années.
Énoncés
Notation Étant donné deux entiers strictement positifs N et i, N s'écrit de façon unique comme une somme de la forme suivante de coefficients binomiaux :
On peut construire ce développement par un algorithme glouton : on choisit pour n le plus grand n tel que , on remplace N par la différence et i par i – 1, et on recommence jusqu'à ce que la différence soit nulle.
Notons
Énoncé pour les complexes simpliciaux
Une suite finie (f = 1, f, … , f) d'entiers strictement positifs est le f-vecteur d'un complexe simplicial de dimension d si et seulement si
Énoncé pour les hypergraphes uniformes Soient N ensembles distincts, chacun à i éléments, et B l'ensemble de toutes les parties à i – r éléments de ces N ensembles. Avec les notations ci-dessus pour le développement de N, on a
Ingrédients de preuve
Pour tout i > 0, on fait la liste L de tous les ensembles de i entiers strictement positifs, par ordre lexicographique en comparant d'abord les plus grands éléments de ces ensembles. Par exemple
Étant donné une suite finie f = (f = 1, f, … , f) d'entiers strictement positifs, soit Δ l'ensemble dont les éléments sont l'ensemble vide et, pour chaque i de 1 à d + 1, les f premiers éléments de la liste L . On démontre alors que les trois conditions suivantes sont équivalentes :
f est le f-vecteur d'un complexe simplicial, Δ est un complexe,
L'implication difficile est 1 ⇒ 2.
Références
Lien externe Kruskal-Katona theorem sur le wiki Projet Polymath
Catégorie:Combinatoire algébrique Catégorie:Hypergraphe Catégorie:Système d'ensembles Kruskal-Katona