Famille de Sperner

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En combinatoire, une famille de Sperner (ou système de Sperner), appelé en l'honneur d'Emanuel Sperner, est un hypergraphe (E, F) (c'est-à-dire un ensemble E et un ensemble F de parties de E) dans lequel aucun élément de F ne contient un autre. Formellement,

Si X, Y sont dans F et X ≠ Y, alors X n'est pas contenu dans Y et Y n'est pas contenu dans X.

De manière équivalente, une famille de Sperner est une antichaîne de l'ensemble des parties (ordonné par l'inclusion) d'un ensemble.

Théorème de Sperner[modifier | modifier le code]

Pour toute famille de Sperner S sur un ensemble X à n éléments,

Ce majorant est optimal, car il est atteint en prenant pour S l'ensemble des parties de X à k éléments, avec k = n/2 si n est pair et k = (n – 1)/2 ou (n + 1)/2 si n est impair. Le théorème de Sperner se reformule donc en disant que la largeur de l'ordre d'inclusion sur l'ensemble des parties de X est égale à cette borne.

Le théorème de Sperner est un cas particulier du théorème de Dilworth. Il est parfois appelé lemme de Sperner, mais ceci peut prêter à confusion avec le lemme de Sperner qui est un autre résultat de combinatoire, sur la coloration de graphe.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sperner family » (voir la liste des auteurs).
  1. (en) D. Lubell, « A short proof of Sperner's theorem », JCT, vol. 1,‎ , p. 299

Articles connexes[modifier | modifier le code]