La propri´et´e de Sperner
Anna Ferretti
10 avril 2014
Dans ce travail on va s’occuper d’un probl`eme de th´eorie des ensembles : pour
un ensemble `
a n ´el´ements, quel est la collection la plus grande de sous-ensembles
telle que aucun des sous-ensembles choisis n’est contenu dans un autre de cette
collection. Ce probl`eme ´equivaut `a dire que l’alg`ebre bool´eenne Bn poss`ede la
propri´et´e de Sperner (Th´eor`eme de Sperner). On donnera donc des preuves de ce
Th´eor`eme en entroduisant les notions d’ensemble partiellement ordonn´e (poset)
et d’alg`ebre bool´eenne.
Ce travail se base sur le livre de Richard P. Stanley [1, p.31-41].
Tout d’abord quelque rappels.
D´
efinition. Un ensemble partiellement ordonn´
e P est un ensemble fini,
avec une relation binaire (not´ee ≤) qui satisfait les axiomes suivants :
1) x ≤ x pour tout x ∈ P (r´eflexive)
2) Si x ≤ y et y ≤ x, alors x = y (antisim´etrique)
3) Si x ≤ y et y ≤ z, alors x ≤ z (transitive).
D´
efinition. Soit S un ensemble `a n ´el´ements et soit P l’ensemble de tous les
sous ensembles de S. Alors P est appel´e alg`
ebre bool´
eenne (finie) de rang
n et est not´e avec Bs .
Dans le cas sp´ecifique o`
u S = {1, 2, ..., n} on notera simplement Bn .
Il existe une fa¸con de repr´esenter les poset avec un dessin ; ceci est appel´e diagramme de Hasse. Dans ce diagramme les ´el´ements de P sont repr´esent´es
par les sommets. Si x < y dans P , alors y sera dessin´e ”en dessus” de x. Ensuite on dessine une arˆete entre x et y, si y recouvre x (i.e. x < y et il n’y a
pas d’´el´ement z ∈ P satisfaisant x < z < y). Pour mieux comprendre on peut
regarder l’exemple pour le diagramme de Hasse de B3 1.
On dit que deux poset P et Q sont isomorphes s’il existe une bijection φ :
P → Q telle que pour x, y ∈ P , x ≤ y si et seulement si φ(x) ≤ φ(y) dans Q.
On peut voir ¸ca en disant que deux poset sont isomorphes si les diagrammes de
Hasse respectifs diff`erent seulement pour le nom des ´el´ements.
D´
efinition. Une chaˆıne C dans un poset P est un sous-ensemble de P totalement ordonn´e, c’est-`
a-dire, pour x et y ∈ C on aura soit x ≤ y soit y ≤ x.
2
Figure 1 – Le diagramme de Hasse de B3 [1, p.34]
Une chaˆıne finie est de longueur n si elle contient n + 1 ´el´ements. Une telle
chaˆıne est de la forme x0 < x1 < ... < xn . Un poset fini est ”grad´
e” de rang
n si toute chaˆıne maximale est de longueur n (o`
u une chaˆıne maximal est une
chaˆıne qui n’est pas contenue dans une plus longue chaˆıne).
Par exemple l’alg`ebre bol´eenne Bn est ”grad´ee” de rang n.
Soit P ”grad´e” de rang n et soit x ∈ P . On dira que x est de rang j si la chaˆıne
la plus longue de P , avec x comme dernier ´el´ement, est de rang j. Le rang de x
sera not´e ρ(x) = j.
Le i-`
eme niveau de P est d´efini par Pj := {x ∈ P : ρ(x) = j}. On obtient
alors que P est une union disjointe
P = P0 ∪ P1 ∪ ... ∪ Pn
et que chaque chaˆıne maximale de P est de la forme x0 < x1 < ... < xn o`
u
ρ(xj ) = j. On notera pj = |Pj |.
Exemple. Soit P = Bn , alors ρ(x) = |x| (la cardinalit´e de x vu comme ensemble) et
n
pj =
.
j
On dit qu’un ensemble ”grad´e” P de rang n est :
– rang-sym´
etrique, si pi = pn−i pour 0 ≤ i ≤ n
– rang-unimodal, si p0 ≤ p1 ≤ ... ≤ pj−1 ≤ pj ≥ pj+1 ≥ pj+2 ≥ ... ≥ pn pour
un certain 0 ≤ j ≤ n.
La suite des rangs p0 , p1 , ..., pn est aussi appel´ee sym´
etrique ou unimodal
(selon le cas).
Exemple. L’ensemble Bn est rang-sym´
etrique et rang-unimodal.
C’est clair, car la suite n0 , n1 , ..., nn (la n-i`eme ligne du triangle de Pascal)
est sym´etrique et unimodale.
3
D´
efinition. Une antichaˆıne dans un poset P est un sous-ensemble A de P
dans lequel aucun ´el´ement n’est comparable `a un autre, c’est-`a-dire, on ne
peut jamais avoir x, y ∈ A avec x < y.
Par exemple, dans un poset P les niveaux Pj sont des antichaˆınes.
Le probl`eme est maintenant de trouver l’antichaˆıne la plus longue dans un poset
P.
Consid´erons l’alg`ebre bol´eenne Bn . Le probl`eme de trouver la plus longue antichaˆıne dans Bn est ´equivalent au probl`eme auquel on s’interesse dans ce travail :
pour un ensemble `
a n ´el´ements, trouver le nombre maximal de sous-ensembles
tel que aucun de ces sous-ensembles n’est contenu dans un autre choisi.
Pour r´esoudre ce probl`eme on pourrait prendre tous les sous-ensembles de car-
n
dinalit´e bn/2c (la partie enti`ere de n/2). Cela nous donnerait un total de bn/2c
sous-ensembles, correspondant `a la cardinalit´e du plus grand niveau Pj de Bn .
La difficult´e est de montrer qu’il n’existe pas une plus grande collection de
sous-ensembles satisfaisant les crit`eres du probl`eme.
D´
efinition. Soit P un poset ”grad´e” de rang n. On dira que P poss`
ede la
propri´
et´
e de Sperner ou que P est un poset Sperner si
max{|A| : A est une antichaˆıne de P } = max{|Pj | : 0 ≤ j ≤ n}.
En d’autres mots, il n’existe pas d’antichaˆıne plus longue que le niveau Pj avec
le plus grand nombre d’´el´ements.
Remarque. Si P est un ensemble de Sperner, alors il peut quand mˆeme y avoir
des antichaˆınes de cardinalit´e maximal qui ne correspondent pas au niveau Pj le
plus grand. La propri´et´e de Sperner nous dit seulement qu’il ne peut pas exister
d’antichaˆınes plus longues.
Exemple. Voici un exemple de poset P qui ne satisfait pas la propri´et´e de
Sperner.
Figure 2 – Le diagramme de Hasse d’un poset P [1, p. 36]
En effet, max{|A| : A antichaˆıne de P } = 4 6= 3 = max{|Pj | : 0 ≤ j ≤ 1}.
Apr`es la d´efinition ci-dessus, on peut dire que r´esoudre notre probl`eme ´equivaut
a montrer le Th´eor`eme de Sperner :
`
4
Th´
eor`
eme 0.1. L’alg`ebre bool´eenne Bn est un ensemble de Sperner.
En effet, si Bn poss`ede la propri´et´e de Sperner on a que la plus longue antichaˆıne
n
dans Bn a la mˆeme cardinalit´e du plus grand niveau de Bn , donc |A| = bn/2c
et on a resoulu notre probl`eme !
Il existe trois preuves c´el`ebres du Th´eor`eme de Sperner. La premi`ere qu’on va
d´ecrire est celle due `
a Emanuel Sperner en 1927 et utilise l’alg`ebre lin´eaire ;
la deuxi`eme trouv´ee par David Lubell en 1966 utilise des arguments de combinatoire ; la troisi`eme est aussi de type combinatoire, mais utilise l’id´ee de la
premi`ere preuve.
D´emonstration. 1. Pour la premi`ere preuve la proc´edure `a suivre sera expos´ee,
mais les diff´erentes assertions ne seront pas d´emontr´ees.
Pour commencer on d´efinit un ”order matching” µ : Pi → Pi+1 comme ´etant
une fonction injective satisfaisant x < µ(x) pour tout x ∈ Pi . On remarque
que si un tel ”order-matching” existe, alors pi ≤ pi+1 (car µ est injective). Le
contraire est pourtant faux : si pi ≤ pi+1 , c’est pas sˆ
ur qu’il existe un ”ordermatching” de Pi vers Pi+1 . De mani`ere similaire on d´efinit un ”order-matching”
µ : Pi → Pi−1 comme ´etant une fonction injective satisfaisant x > µ(x) pour
tout x ∈ Pi .
Pour d´emontrer notre Th´eor`eme de Sperner on utilise la proposition suivante
qui nous dit que des poset avec une certaine propri´et´e sont Sperner.
Proposition 0.2. Soit P un poset ”grad´e” de rang n. S’il existe un entier
0 ≤ j ≤ n et des ”order-matchings”
P0 → P1 → P2 → ... → Pj ← Pj+1 ← Pj+2 ← ... ← Pn
alors P est rang-unimodal et Sperner.
Il faut maintenant prouver que cette proposition peut ˆetre appliqu´ee `a l’alg`ebre
bool´eenne Bn . Pour faire ¸ca on utilise le Lemme suivant nous garantissant que,
sous certaines conditions, pour un poset P de rang n, il existe des ”ordermatchings” µ : Pi → Pi+1 et µ : Pi+1 → Pi .
Lemme 0.3. Soit RPi l’espace vectoriel r´eel form´e par toutes les combinaisons lin´eaires des ´el´ements de Pi .
i) Supposons qu’il existe une transformation lin´eaire U : RPi → RPi+1 injective
telle que U est un ”order-raising operator”, c’est-`
a-dire, telle que pour tout
x ∈ Pi , U (x) est une combinaison
lin´
e
aire
d’´
e
l´
e
ments
y ∈ Pi+1 satisfaisant
P
x < y (on aurait U (x) = y>x cy y, pour cy ∈ R).
Alors il existe un ”order-matching” µ : Pi → Pi+1 .
ii) De mani`ere similaire, supposons qu’il existe une transformation lin´eaire U :
RPi → RPi+1 surjective qui est un ”order-raising operator”.
Alors il existe un ”order-matching” µ : Pi+1 → Pi .
` ce moment il faut appliquer le Lemme `a l’alg`ebre bool´eenne Bn . Ensuite on
A
pourra directement appliquer la proposition et on obtient que Bn est Sperner !
5
Pour faire ¸ca il faut d´efinir une transformation lin´eaire Ui : R(Bn )i → R(Bn )i+1
pour chaque 0 ≤ i < n, tel qu’elle satisfait les propri´et´ees du Lemme. On va
d´efinir Ui de la mani`ere la plus simple : pour x ∈ (Bn )i soit
X
Ui (x) =
y.
y∈(Bn )i+1 ,y>x
Par d´efinition notre Ui est d´ej`
a un ”order-raising operator”. On veut alors montrer que Ui est injective pour i < n/2 et surjective pour i ≥ n/2. Pour cela il y
a le Th´eor`eme suivant :
Th´
eor`
eme 0.4. L’op´erateur Ui , d´efinit comme ci-dessus, est injectif pour i <
n/2 et surjectif pour i ≥ n/2.
On peut donc utiliser l’op´erateur Ui d´efinit avant pour appliquer le Lemme `a
l’alg`ebre bool´eenne Bn et c’est bon :)
Cette premi`ere d´emonstration est tr`es indirecte et longue. Lubell a essay´e de
resoudre c¸a autrement et on va maintenant donner sa preuve (beaucoup plus
courte, simple et jolie).
D´emonstration. 2. On sait que le nombre maximal d’´el´ements d’un niveau Pj
n
de Bn est bn/2c
. Les niveaux sont des antichaˆınes, donc pour une antichaˆıne
A de cardinalit´e maximale on a
n
|A| ≥
.
bn/2c
n
Ce qu’il faut montrer maintenant est |A| ≤ bn/2c
.
On commence par compter le nombre total de chaˆınes maximales ∅ = x0 < x1 <
... < xn = {1, ..., n} dans Bn : il y a n choix pour x1 , ensuite n − 1 choix pour
x2 et ainsi de suite. En total il y a donc n! chaˆınes maximales. Ensuite il faut
compter le nombre total de chaˆınes maximales ∅ = x0 < x1 < ... < xi = x <
xi+1 < ... < xn = {1, ..., n} qui contiennent un ´el´ement x donn´e, de rang i. Il y
a i choix pour x1 , i − 1 choix pour x2 , jusqu’`a un choix pour xi = x. Ensuite il
y a n − i choix pour xi+1 , n − i − 1 choix pour xi+2 , etc. jusqu’`a un choix pour
xn . Le nombre de chaˆınes maximales contenant x est donc i!(n − i)!.
Maintenant soit A une antichaˆıne. Pour x ∈ A soit Cx l’ensemble des chaˆınes
maximales de Bn qui contiennent x. Puisque x ∈ A, les ensembles Cx sont
deux `
a deux disjoints (par la d´efinition d’une antichaˆıne). En effet pour tout
x1 , x2 ∈ A : toute chaˆıne c ∈ Cx1 contient x1 . Cela implique que c ne contient
pas x2 . De mˆeme, toute chaˆıne c0 ∈ Cx2 contient x2 . Donc c 6= c0 pour tout
c ∈ Cx1 , c0 ∈ Cx2 .
Vu que les Cx sont disjoints on obtient :
[
X
X
|
Cx | =
|Cx | =
(ρ(x))!(n − ρ(x))!
x∈A
x∈A
x∈A
Le nombre de chaˆınes maximales dans les Cx ne peut pas d´epasser le nombre
total de chaˆınes maximales dans Bn , qui a ´et´e calcul´e comme ´etant n!. On a
donc
X
(ρ(x))!(n − ρ(x))! ≤ n!.
x∈A
´ ERENCES
´
REF
6
On divise par n! des deux cˆ
ot´es et on obtient
X 1
≤ 1.
n
x∈A
ρ(x)
n
Le coefficient binomial i atteint son maximum en i = bn/2c. Cela nous donne
1
≤ n1 pour tout x ∈ Bn . En revenant `a notre calcul on obtient
n
(bn/2c
)
(ρ(x))
X
X 1
1
≤
≤1
n
n
x∈A
bn/2c
x∈A
ρ(x)
ce qui est ´equivalent `
a
n
|A| ≤
.
bn/2c
On a donc obtenu ce qu’on voulait. Le Th´eor`eme de Sperner est ainsi d´emontr´e !
La troisi`eme preuve reprend l’id´ee de la premi`ere en utilisant les ”order-matchings”.
D´emonstration. 3. Dans cette d´emonstration on d´efinit explicitement un ”ordermatching” µ : (Bn )i → (Bn )i+1 pour i < n/2 de la mani`ere suivante. Chaque
S ∈ (Bn )i est repr´esent´e par une suite de +1 et −1, construite en prenant une
suite (a1 , a2 , ..., an ) o`
u aj = 1 si j ∈ S et aj = −1 si j n’appartient pas `a S.
Dans cette s´equence on remplace ensuite chaque +1 et −1 cons´ecutifs par deux
z´eros 00. On r´ep`ete se processus, en ignorant les 00, jusqu’`a quand il n’y a plus
rien `
a remplacer. On d´efinit alors µ(S) = S ∪ {k} o`
u k repr´esente la derni`ere
position occup´ee par un −1. µ d´efinie de cette mani`ere nous donne bien un
”order-matching”. Ensuite, si on relie tous les ”order-matchings” pour i < n/2
et on les relie aussi, par une construction sym´etrique, aux ”order-matchings”
(Bn )i → (Bn )i−1 pour i > n/2 on obtient les order-matchings de la Proposition
0.2
(Bn )0 → (Bn )1 → (Bn )2 → ... → (Bn )j ← (Bn )j+1 ← (Bn )j+2 ← ... ← (Bn )n
et on a d´emontr´e que Bn est Sperner.
Dans ce travail on a ainsi d´emontr´e un important probl`eme de la Th´eorie des
ensembles, celui o`
u pour un ensemble `a n ´el´ements il faut trouver la collection
avec le plus grand nombre de sous-ensembles tel que aucun des sous-ensembles
soit contenu dans un autre de cette collection. Le Th´eor`eme de Sperner est
´equivalent `
a r´esoudre ce probl`eme, donc on en a donn´e quelque preuve. La
premi`ere (due `
a Sperner) a ´et´e illustr´ee pour son importance dans d’autres
r´esultats de combinatoire. En effet, dans certains cas on ne connaˆıt pas de
preuves simples et directes, donc les ”order-raising operators” Ui et le Th´eor`eme
0.4 de la premi`ere d´emonstration se r´ev`elent tr`es utiles.
R´
ef´
erences
[1] Richard P. Stanley. Algebraic Combinatorics. Undergraduate Texts in Mathematics. Springer, New York, 2013.
© Copyright 2024 ExpyDoc
