Famille de Sperner

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Sperner.

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]