Accueil🇫🇷Chercher

Famille de 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

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

(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

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