Sperner family

Prenons quatre éléments nommés a, b, c et d, puis formons tous les groupes de deux. Il y en a six : {a, b}, {a, c}, {a, d}, {b, c}, {b, d} et {c, d}. Aucun de ces groupes ne peut en contenir un autre, puisqu'ils ont tous deux éléments et sont distincts. Cette collection forme donc une famille de Sperner : ses membres restent incomparables par inclusion.

Soit E un ensemble fini et soit F une collection de sous-ensembles de E. La collection F est une famille de Sperner, aussi appelée antichaîne, lorsque deux membres distincts de F ne sont jamais comparables par inclusion. Autrement dit, si X et Y appartiennent à F et sont distincts, ni X ⊆ Y ni Y ⊆ X.

Le nombre d'éléments de E est noté n. Le théorème de Sperner donne alors la plus grande taille possible de F :Le symbole ⌊n/2⌋ désigne la partie entière de n/2. La borne est atteinte en prenant tous les sous-ensembles de E qui possèdent exactement ⌊n/2⌋ éléments. Deux ensembles distincts de même taille ne peuvent en effet s'inclure l'un dans l'autre.

Pour n = 4, le niveau des sous-ensembles à deux éléments contient C(4, 2) = 6 membres. Il fournit donc une antichaîne de taille maximale, celle qui sert d'exemple dans cette fiche.

Considérons l'ensemble E = {a, b, c, d}. Il possède n = 4 éléments. La collection étudiée est F = {{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}} : elle réunit exactement tous les sous-ensembles de E à deux éléments.

1. On compare deux membres distincts de F. Chacun contient deux éléments ; si l'un était inclus dans l'autre, ils seraient nécessairement égaux. Ils sont donc incomparables, et F est une famille de Sperner.

2. On compte les choix de deux éléments parmi quatre :La collection comporte bien les six paires annoncées.

3. Le théorème de Sperner donne la même valeur maximale, car ⌊4/2⌋ = 2. Ainsi, F n'est pas seulement une antichaîne : aucune antichaîne de sous-ensembles de E ne peut avoir plus de six membres. Le contrôle est refaisable en vérifiant les six paires et l'absence d'inclusion entre deux paires distinctes.

Pour tester une collection, on cherche une paire de membres comparables. Dès que X ⊆ Y avec X et Y distincts, la collection n'est pas une famille de Sperner. Si la collection est courte, cette comparaison directe est préférable à un calcul de taille, qui ne prouve pas l'incomparabilité.

Pour construire une grande antichaîne sur n éléments, on réunit tous les sous-ensembles ayant ⌊n/2⌋ éléments. Le critère observable est leur taille commune : deux membres distincts ne peuvent alors pas s'inclure. Pour n = 4, cette construction redonne les six paires de l'exemple.

Pour évaluer une famille proposée, on compare son nombre de membres à C(n, ⌊n/2⌋). Dépasser cette valeur est impossible pour une antichaîne. Atteindre la borne établit une taille maximale seulement après avoir vérifié la condition d'incomparabilité.

Une chaîne regroupe au contraire des ensembles comparables deux à deux par inclusion. Ainsi, ∅ ⊆ {a} ⊆ {a, b} forme une chaîne, tandis que {{a, b}, {a, c}} forme une antichaîne. Le test consiste donc à chercher des inclusions, avec un verdict opposé dans les deux notions.

Une famille de Sperner n'est pas une famille d'ensembles deux à deux disjoints. Les ensembles {a, b} et {a, c} ont l'élément a en commun, mais aucun ne contient l'autre : ils peuvent appartenir à la même antichaîne. Le critère porte sur l'inclusion, pas sur l'intersection.

Des membres de tailles différentes peuvent former une antichaîne. Par exemple, {a} et {b, c} sont incomparables si a, b et c sont distincts. Une taille commune garantit l'incomparabilité entre membres distincts, mais elle n'est pas une condition nécessaire.

Il faut distinguer maximale par ajout et de taille maximum. Sur E = {a, b}, la famille {∅} ne peut accueillir aucun autre sous-ensemble, puisque ∅ est inclus dans chacun d'eux : elle est maximale par ajout. Elle n'a pourtant qu'un membre, contre deux pour {{a}, {b}}. Le théorème de Sperner porte sur la plus grande taille possible.

Une collection vide satisfait la condition d'incomparabilité, puisqu'elle ne contient aucune paire à comparer. Elle est donc une famille de Sperner, mais elle n'atteint pas la taille maximum dès qu'un sous-ensemble de E peut être choisi.

Lorsque E est vide, il possède un unique sous-ensemble, ∅. La famille {∅} est alors une antichaîne de taille 1, en accord avec C(0, 0) = 1. Ce cas charnière rappelle que l'ensemble vide peut être membre d'une antichaîne, mais jamais avec un autre sous-ensemble qu'il inclurait.

L'article Inclusion précise la relation X ⊆ Y qui sert à comparer les membres d'une collection et à repérer une antichaîne.

La fiche Ordre partiel replace les antichaînes dans le cadre général où certains éléments peuvent être incomparables.