title: Théorème de Kruskal-Katona
text: # Théorème de Kruskal-Katona
  
  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={\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.$
  
  On peut construire ce développement par un algorithme glouton : on choisit pour $n_i$ le plus grand n tel que $\scriptstyle N\geq {\binom {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)}={\binom {n_{i}}{i+1}}+{\binom {n_{i-1}}{i}}+\ldots +{\binom {n_{j}}{j+1}}.$
  
  ### Énoncé pour les complexes simpliciaux
  
  Une suite finie $(f_0$ = 1, $f_1,$ … , $f_{d+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}\leq 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|\geq {\binom {n_{i}}{i-r}}+{\binom {n_{i-1}}{i-r-1}}+\ldots +{\binom {n_{j}}{j-r}}.$
  
  ## Ingrédients de preuve
  
  Pour tout i > 0, on fait la liste $L_i$ 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é une suite finie f = $(f_0$ = 1, $f_1,$ … , $f_{d+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 $f_{i–1}$ premiers éléments de la liste $L_i$ . On démontre alors que les trois conditions suivantes sont équivalentes :
  
  * f est le f-vecteur d'un complexe simplicial,
  * $Δ_f$ est un complexe,
  * $\forall i\in \{1,\ldots ,d+1\},\quad f_{i}\leq f_{i-1}^{(i)}.$
  
  L'implication difficile est 1 ⇒ 2.
  
  