Famille de Sperner

En combinatoire, une famille de Sperner (ou système de Sperner), appelé ainsi 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 inclus dans Y et Y n'est pas inclus dans X.

De manière équivalente, une famille de Sperner (ou ensemble de Sperner) est une antichaîne de l'ensemble des parties (ordonné par l'inclusion) d'un ensemble.

Exemples

Toute partie de ${\displaystyle {\mathcal {P}}_{k}(X)}$, ensemble des parties à k éléments d'un ensemble X à n éléments est un ensemble de Sperner sur X.

Nombre d'ensembles de Sterner sur un ensemble à n éléments

Le nombre d'ensembles de Sterner sur un ensemble à n éléments est appelé nombre de Dedekind d'ordre n et noté ${\displaystyle M(n)}$; ils forment la suite débutant par 2, 3, 6, 20, 168 ; voir la suite A000372 de l'OEIS,.

D'après ce qui précède, ${\displaystyle M(n)}$ est supérieur ou égal au nombre d'ensembles formés de parties de X ayant le même nombre d'éléments, soit ${\displaystyle M(n)\geqslant \sum _{k=0}^{n}2^{\binom {n}{k}}-n}$ ; voir la suite A169974 de l'OEIS.

Théorème de Sperner

Pour tout ensemble de Sperner S sur un ensemble X à n éléments,

${\displaystyle |S|\leqslant {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 [1].

Démonstration

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

${\displaystyle {n \choose \lfloor {n/2}\rfloor }\geqslant {n \choose k}}$

et donc,

${\displaystyle {s_{k} \over {n \choose \lfloor {n/2}\rfloor }}\leqslant {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

${\displaystyle \sum _{k=0}^{n}{s_{k} \over {n \choose \lfloor {n/2}\rfloor }}\leqslant \sum _{k=0}^{n}{s_{k} \over {n \choose k}}\leqslant 1,}$

ce qui s'écrit

${\displaystyle |S|=\sum _{k=0}^{n}s_{k}\leqslant {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).

1. Martin Aigner, Günter M. Ziegler, Raisonnements divins, Springer, 2013, p. 201-202
2. (en) D. Lubell, « A short proof of Sperner's theorem », JCT, vol. 1,‎ 1966, p. 299

Articles connexes

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