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,

|S| \le {n \choose \lfloor{n/2}\rfloor}.

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.

Preuve[modifier | modifier le code]

Cette preuve est due à Lubell[1]. Soit sk le nombre d'ensembles à k éléments de S. Pour tout 0 ≤ kn,

{n \choose \lfloor{n/2}\rfloor} \ge {n \choose k}

et donc,

{s_k \over {n \choose \lfloor{n/2}\rfloor}} \le {s_k \over {n \choose k}}.

Comme S est une antichaîne, on peut sommer les précédentes inégalités de k = 0 à n et ensuite appliquer l'inégalité de Lubell-Yamamoto-Meshalkin pour obtenir

\sum_{k=0}^n{s_k \over {n \choose \lfloor{n/2}\rfloor}} \le \sum_{k=0}^n{s_k \over {n \choose k}} \le 1,

ce qui s'écrit

 |S| = \sum_{k=0}^n s_k \le {n \choose \lfloor{n/2}\rfloor}.

Ceci termine la preuve.

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.

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

  1. (en) D. Lubell, « A short proof of Sperner's theorem », JCT, vol. 1,‎ 1966, p. 299

(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)

Articles connexes[modifier | modifier le code]