Famille de sperner

Famille de Sperner

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

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}.$

Preuve

Cette preuve est due à 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 ingalité 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}$.

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.

Références

Lubell, D. (1966). A short proof of Sperner's theorem, J. Combin. Theory 1, 299.

Ce document provient de « Famille de Sperner ».