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,

$|S|\leq {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.

Démonstration

Cette preuve est due à Lubell. Soit s_k le nombre d'ensembles à k éléments de S. Pour tout 0 ≤ k ≤ n,

${n \choose \lfloor {n/2}\rfloor }\geq {n \choose k}$

et donc,

${s_{k} \over {n \choose \lfloor {n/2}\rfloor }}\leq {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 }}\leq \sum _{k=0}^{n}{s_{k} \over {n \choose k}}\leq 1,$

ce qui s'écrit

$|S|=\sum _{k=0}^{n}s_{k}\leq {n \choose \lfloor {n/2}\rfloor }$.

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

Articles connexes

• Nombre de DedekindNombre de Dedekind
• Théorème d'Erdős-Ko-Rado