Famille de Sperner

Modèle:Voir homonymes Modèle:Ébauche 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 ${𝒫}_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é $M(n)$; ils forment la suite débutant par 2, 3, 6, 20, 168 ; voir la Modèle:OEIS,.

D'après ce qui précède, $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 $M(n)⩾\sum _{k=0}^n{2}^{(\genfrac{}{}{0ex}{}{n}{k})}-n$ ; voir la Modèle:OEIS.

Théorème de Sperner

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

$|S|⩽(\genfrac{}{}{0ex}{}{n}{\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 .

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.

Articles connexes

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