Théorème de Kruskal-Katona

Modèle:Voir homonyme 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 :

$N=(\genfrac{}{}{0ex}{}{n_i}{i})+(\genfrac{}{}{0ex}{}{n_{i-1}}{i-1})+\dots +(\genfrac{}{}{0ex}{}{n_j}{j}),n_i>n_{i-1}>\dots >n_j\ge j\ge 1.$

On peut construire ce développement par un algorithme glouton : on choisit pour nModèle:Ind le plus grand n tel que $N\ge (\genfrac{}{}{0ex}{}{n}{i})$, on remplace N par la différence et i par i – 1, et on recommence jusqu'à ce que la différence soit nulle.

Notons

$N^{(i)}=(\genfrac{}{}{0ex}{}{n_i}{i+1})+(\genfrac{}{}{0ex}{}{n_{i-1}}{i})+\dots +(\genfrac{}{}{0ex}{}{n_j}{j+1}).$

Énoncé pour les complexes simpliciaux

Une suite finie (fModèle:Ind = 1, fModèle:Ind, … , fModèle:Ind) d'entiers strictement positifs est le f-vecteur d'un complexe simplicial de dimension d si et seulement si

$\mathrm{\forall }i\in \{1,\dots ,d+1\},f_i\le f_{i-1}^{(i)}.$

É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

$|B|\ge (\genfrac{}{}{0ex}{}{n_i}{i-r})+(\genfrac{}{}{0ex}{}{n_{i-1}}{i-r-1})+\dots +(\genfrac{}{}{0ex}{}{n_j}{j-r}).$

Ingrédients de preuve

Pour tout i > 0, on fait la liste LModèle:Ind 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

$L_3=(\{3,2,1\},\{4,2,1\},\{4,3,1\},\{4,3,2\},\{5,2,1\},\{5,3,1\},\{5,3,2\},\{5,4,1\},\{5,4,2\},\{5,4,3\}\dots ).$

Étant donné une suite finie f = (fModèle:Ind = 1, fModèle:Ind, … , fModèle:Ind) d'entiers strictement positifs, soit ΔModèle:Ind l'ensemble dont les éléments sont l'ensemble vide et, pour chaque i de 1 à d + 1, les fModèle:Ind premiers éléments de la liste LModèle:Ind . On démontre alors que les trois conditions suivantes sont équivalentes :

1. f est le f-vecteur d'un complexe simplicial,
2. ΔModèle:Ind est un complexe,
3. $\mathrm{\forall }i\in \{1,\dots ,d+1\},f_i\le f_{i-1}^{(i)}.$

L'implication difficile est 1 ⇒ 2.

Références

• Modèle:Chapitre
• Modèle:Chapitre
• Modèle:OuvrageModèle:Commentaire biblio
• Modèle:Ouvrage

Lien externe

Modèle:En Kruskal-Katona theorem sur le wiki Projet Polymath