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 , 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é ; 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, est supérieur ou égal au nombre d'ensembles formés de parties de X ayant le même nombre d'éléments, soit ; 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,
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.
Notes et références
Articles connexes
- Nombre de Dedekind
- Théorème d'Erdős-Ko-Rado
- Portail des mathématiques
