- 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.
Sommaire
Théorème de Sperner
Pour toute famille de Sperner S sur un ensemble à n éléments
Preuve
Cette preuve est due à Lubell[1]. Soit sk le nombre d'ensemble à k éléments de S. Pour tout 0 ≤ k ≤ n,
et donc,
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 (en) pour obtenir
ce qui s'écrit
- .
Ceci termine la preuve.
Le théorème de Sperner est un cas particulier du théorème de Dilworth (en). 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
- Lubell, D. (1966). A short proof of Sperner's theorem, J. Combin. Theory 1, 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)
Voir aussi
Nombre de Dedekind (en)
Wikimedia Foundation. 2010.