Famille de Sperner

Un article de Wikipédia, l'encyclopédie libre.

En combinatoire, une famille de Sperner (ou système de Sperner), appelé en l'honneur d'Emanuel Sperner, est système d'ensembles (F, E) dans lequel aucun élément 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 continu dans X.

De manière équivalente, une famille de Sperner est une antichaîne sur des treillis inclus sans des puissance cartésienne de E.

[modifier] Théorème de Sperner

Pour toute famille de Sperner S sur un ensemble à n éléments

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

[modifier] Preuve

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

${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 antichaine, on peut sommer les précédentes inégalités de k=0 à n et ensuite appliquer ingélité de Lubell-Yamamoto-Meshalkin inequality 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}$ .

Ce qui termine la preuve.

Le théorème de Sperner peut être vu comme un cas spécial du théorème Dilworth. Il est parfois appelé à tort Lemme de Sperner, car ceci fait référence à un autre résultat de combinatoire sur la coloration de graphe.