Exercice 20

1. La famille $\{\varnothing\}$, ou toute famille réduite à une partie, est une antichaîne de cardinal $1$. La famille des singletons $\big\{\{1\}, \dots, \{n\}\big\}$ en est une de cardinal $n$, car aucun singleton n'est inclus dans un autre. Plus généralement, pour $k \in \llbracket 0\,,n \rrbracket$, la famille de toutes les parties à $k$ éléments est une antichaîne : si $A \subset B$ avec $|A| = |B|$, alors $A = B$ (proposition 1 (ii)). Son cardinal est $\binom{n}{k}$, maximal pour $k = \lfloor \frac{n}{2} \rfloor$ (exercice 28 de la feuille du chapitre 3). Pour $n = 4$, la famille $\big\{\{1, 2\}, \{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}\big\}$ est une antichaîne à $6$ éléments. On peut aussi mélanger les cardinaux, comme $\big\{\{1\}, \{2, 3\}\big\}$ pour $n = 3$.

2.(a) Si $C_{k-1} \subsetneq C_{k}$, alors $|C_{k-1}| < |C_{k}|$ (proposition 1 (ii)), donc $|C_{k}| \geqslant |C_{k-1}| + 1$, puisque ce sont des entiers. Par récurrence, $|C_{k}| \geqslant |C_{0}| + k \geqslant k$ et $|C_{k}| \leqslant |C_{n}| - (n - k) \leqslant k$. $$\boxed{|C_{k}| = k \text{ pour tout } k \in \llbracket 0\,,n \rrbracket}$$ En particulier $C_{0} = \varnothing$ et $C_{n} = \llbracket 1\,,n \rrbracket$, et, pour $k \geqslant 1$, $C_{k} \setminus C_{k-1}$ est un singleton $\{x_{k}\}$. Les éléments $x_{1}$, …, $x_{n}$ sont deux à deux distincts, puisque $x_{k} \notin C_{k-1}$ alors que $x_{j} \in C_{k-1}$ pour $j < k$, et $C_{k} = \{x_{1}, \dots, x_{k}\}$. L'application qui associe à une chaîne complète la liste $(x_{1}, \dots, x_{n})$ est une bijection de l'ensemble des chaînes complètes sur l'ensemble des $n$-listes d'éléments distincts de $\llbracket 1\,,n \rrbracket$ : sa réciproque associe à une liste la chaîne des $C_{k} = \{x_{1}, \dots, x_{k}\}$. Par le théorème 1 : $$\boxed{n! \text{ chaînes complètes}}$$ On construit une chaîne en ajoutant les éléments un par un, dans un ordre choisi.

2.(b) Soit $X$ une partie, de cardinal $k$. Par la question (a), $X$ ne peut être que le terme $C_{k}$ d'une chaîne, et $C_{k} = X$ si et seulement si $\{x_{1}, \dots, x_{k}\} = X$ : la liste commence par une énumération des éléments de $X$, en $k!$ ordres possibles, et se termine par une énumération de $\overline{X}$, en $(n - k)!$ ordres. $$\boxed{|X|!\,\big(n - |X|\big)! \text{ chaînes complètes passent par } X}$$

La figure représente les parties de $\llbracket 1\,,3 \rrbracket$, chaque trait reliant une partie à une partie qui a un élément de plus. Une chaîne complète, en bleu, monte du bas vers le haut en ajoutant $2$, puis $3$, puis $1$ : il y en a $3! = 6$, une par ordre d'ajout. Elle traverse l'antichaîne des parties à deux éléments, en ocre, en un seul point, $\{2, 3\}$.

3. Pour $A \in \mathcal{A}$, notons $\mathcal{K}_{A}$ l'ensemble des chaînes complètes qui passent par $A$. Si une chaîne passait par deux éléments distincts $A$ et $A'$ de $\mathcal{A}$, l'un serait inclus dans l'autre, puisque deux termes d'une chaîne sont toujours comparables pour l'inclusion : c'est exclu dans une antichaîne. Les ensembles $\mathcal{K}_{A}$, pour $A \in \mathcal{A}$, sont donc deux à deux disjoints, et leur réunion est contenue dans l'ensemble des $n!$ chaînes complètes. Les propositions 2 (i) et 1 (ii), avec la question 2, donnent $$\boxed{\sum_{A \in \mathcal{A}} |A|!\,\big(n - |A|\big)! = \sum_{A \in \mathcal{A}} |\mathcal{K}_{A}| \leqslant n!}$$

4. En divisant par $n!$, l'inégalité s'écrit $\sum_{A \in \mathcal{A}} \binom{n}{|A|}^{-1} \leqslant 1$. Posons $M = \binom{n}{\lfloor n/2 \rfloor}$. Par l'exercice 28 de la feuille du chapitre 3, $\binom{n}{k} \leqslant M$ pour tout $k \in \llbracket 0\,,n \rrbracket$, donc chaque terme de la somme est au moins égal à $\frac{1}{M}$, et $\frac{|\mathcal{A}|}{M} \leqslant 1$. La famille des parties à $\lfloor \frac{n}{2} \rfloor$ éléments est une antichaîne de cardinal $M$ (question 1) : la borne est atteinte. $$\boxed{\text{Le cardinal maximal d'une antichaîne de parties de } \llbracket 1\,,n \rrbracket \text{ est } \binom{n}{\lfloor n/2 \rfloor}}$$ Une recherche exhaustive parmi toutes les familles de parties confirme les maxima $1$, $2$, $3$ et $6$ pour $n = 1$, $2$, $3$, $4$.

À retenir. La démonstration de Lubell, Yamamoto et Meshalkin est un double comptage : on compte les couples (chaîne, élément de l'antichaîne situé sur la chaîne), une fois selon la chaîne, chacune portant au plus un élément, une fois selon l'élément. On peut la lire en probabilités : si l'on choisit une chaîne complète au hasard, sous la probabilité uniforme, elle passe par $A$ avec probabilité $\binom{n}{|A|}^{-1}$, et les événements correspondants sont deux à deux incompatibles ; leur somme est donc au plus $1$.