Théorème de Kruskal-Katona

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour l’article homonyme, voir Théorème de Kruskal

En combinatoire algébrique, le théorème de Kruskal-Katona, nommé d'après Joseph Kruskal et Gyula O. H. Katona (en), 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[modifier | modifier le code]

Notation[modifier | modifier le code]

Étant donnés 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=\binom{n_i}i+\binom{n_{i-1}}{i-1}+\ldots+\binom{n_j}j,\quad n_i>n_{i-1}>\ldots>n_j\ge j\ge1.

On peut construire ce développement par un algorithme glouton : on choisit pour ni le plus grand n tel que \scriptstyle N\ge\binom ni, 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)}=\binom{n_i}{i+1}+\binom{n_{i-1}}{i}+\ldots+\binom{n_j}{j+1}.

Énoncé pour les complexes simpliciaux[modifier | modifier le code]

Une suite finie (f0 = 1, f1, … , fd + 1) d'entiers strictement positifs est le f-vecteur d'un complexe simplicial de dimension d si et seulement si

\forall i\in\{1,\ldots,d+1\},\quad f_i\le f_{i-1}^{(i)}.

Énoncé pour les hypergraphes uniformes[modifier | modifier le code]

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\binom{n_i}{i-r}+\binom{n_{i-1}}{i-r-1}+\ldots+\binom{n_j}{j-r}.

Ingrédients de preuve[modifier | modifier le code]

Pour tout i > 0, on fait la liste Li 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\}\ldots).

Étant donnée une suite finie f = (f0 = 1, f1, … , fd + 1) d'entiers strictement positifs, soit Δf l'ensemble dont les éléments sont l'ensemble vide et, pour chaque i de 1 à d + 1, les fi – 1 premiers éléments de la liste Li . On démontre alors que les trois conditions suivantes sont équivalentes :

  1. f est le f-vecteur d'un complexe simplicial,
  2. Δf est un complexe,
  3. \forall i\in\{1,\ldots,d+1\},\quad f_i\le f_{i-1}^{(i)}.

L'implication difficile est 1 ⇒ 2.

Références[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Kruskal-Katona theorem sur le wiki Projet Polymath