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₀ = 1, f₁, … , 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₀ = 1, f₁, … , 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.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Kruskal–Katona theorem » (voir la liste des auteurs).
(en) J. B. Kruskal, « The number of simplices in a complex », dans R. Bellman, Mathematical Optimization Techniques, University of California Press, 1963
(en) G. O. H. Katona, « A theorem of finite sets », dans P. Erdős et G. O. H. Katona, Theory of Graphs, Akadémiai Kiadó and Academic Press, 1968
(en) D. Knuth, The Art of Computer Programming, ps (lire en ligne), « Prefascicle 3a (A draft of section 7.2.1.3): Generating all combinations »
Contient une démonstration via un théorème plus général de géométrie discrète
(en) Richard Stanley, Combinatorics and commutative algebra, Birkhäuser, coll. « Progress in Mathematics » (n^o 41), 1996, 2^e éd. (ISBN 0-8176-3836-9)

Lien externe

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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.