Accueil🇫🇷Chercher

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 :

On peut construire ce développement par un algorithme glouton : on choisit pour ni 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 (f0 = 1, f1, … , fd + 1) 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 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

Étant donné 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,

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,
  • (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,
  • (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 » (no 41), , 2e é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.