§E13.6Sperner の定理と LYM 不等式

証明. (1)の必要性.$\mathcal C$を極大鎖とする。$\mathcal C$の任意の二元は包含に関して比較可能であるから、$\mathcal C$の元を濃度の小さい順に$C_0\subsetneq C_1\subsetneq\dots\subsetneq C_r$と並べることができる。

$C_0=\varnothing$である。実際、$C_0\ne\varnothing$ならば$\varnothing$は$\mathcal C$のすべての元に含まれるので$\mathcal C\cup\{\varnothing\}$は鎖であり、$\varnothing\notin\mathcal C$（$\mathcal C$の元のうち濃度が最小のものが$C_0\ne\varnothing$である）とあわせて$\mathcal C$を真に含む鎖となり、極大性に反する。同様に$C_r=[n]$である。

各$i$について$\lvert C_{i+1}\rvert=\lvert C_i\rvert+1$である。実際、$\lvert C_{i+1}\rvert\ge\lvert C_i\rvert+2$と仮定して$x\in C_{i+1}\setminus C_i$を一つ取り、$D=C_i\cup\{x\}$と置くと、$C_i\subsetneq D\subsetneq C_{i+1}$である。$j\le i$のとき$C_j\subseteq C_i\subseteq D$であり、$j\ge i+1$のとき$D\subseteq C_{i+1}\subseteq C_j$であるから、$D$は$\mathcal C$のすべての元と比較可能であり、$\mathcal C\cup\{D\}$は鎖である。さらに$D\notin\mathcal C$である。実際、$\mathcal C$の元の濃度は$\lvert C_0\rvert<\lvert C_1\rvert<\dots<\lvert C_r\rvert$と狭義単調に並び、$\lvert C_i\rvert<\lvert D\rvert<\lvert C_{i+1}\rvert$を満たす濃度をもつ$\mathcal C$の元は存在しないからである。ゆえに$\mathcal C\cup\{D\}$は$\mathcal C$を真に含む鎖であり、極大性に反する。

$\lvert C_0\rvert=0$、$\lvert C_r\rvert=n$、および濃度が一つずつ増えることから$r=n$かつ$\lvert C_i\rvert=i$を得る。

(1)の十分性.$\mathcal C=\{C_0,\dots,C_n\}$が$C_0\subsetneq\dots\subsetneq C_n$かつ$\lvert C_i\rvert=i$を満たすとする。$\mathcal C$は鎖である。極大性を示すために、$B\subseteq[n]$が$\mathcal C$のすべての元と比較可能であるとする。$k=\lvert B\rvert$と置くと$0\le k\le n$であり、$B$と$C_k$は比較可能であるから$B\subseteq C_k$または$C_k\subseteq B$が成り立つ。いずれの場合も$\lvert B\rvert=\lvert C_k\rvert=k$と有限性から$B=C_k\in\mathcal C$である。ゆえに$\mathcal C$を真に含む鎖は存在しない。

(2)を示す。 極大鎖$\mathcal C=\{C_0,\dots,C_n\}$に対し、$C_i\setminus C_{i-1}$は$(1)$より一元集合であるから、その元を$\sigma(i)$と書いて写像$\sigma\colon[n]\to[n]$を定める。集合$C_1\setminus C_0,\dots,C_n\setminus C_{n-1}$は互いに素であるから$\sigma$は単射であり、これらの合併が$C_n\setminus C_0=[n]$に等しいから$\sigma$は全射である。ゆえに$\sigma$は$[n]$の順列である。

逆に$[n]$の順列$\sigma$に対し$C_i=\{\sigma(1),\dots,\sigma(i)\}$（$C_0=\varnothing$）と定めると、$\lvert C_i\rvert=i$かつ$C_{i-1}\subsetneq C_i$であるから$(1)$より$\{C_0,\dots,C_n\}$は極大鎖である。二つの対応が互いに逆であることは、いずれの向きも$C_i=\{\sigma(1),\dots,\sigma(i)\}$という関係で結ばれることから従う。ゆえに極大鎖の全体と順列の全体の間に全単射が存在する。

§D2.2 命題 3.1より$[n]$の順列の総数は$n!$であり、§D2.2 命題 1.5より極大鎖の総数も$n!$である。

(3)を示す。 極大鎖$\mathcal C$が$A$を元としてもつことと$C_k=A$が成り立つことは同値である。実際、$A\in\mathcal C$ならば$A=C_{\lvert A\rvert}=C_k$であり、逆は明らかである。$(2)$の全単射のもとで、条件$C_k=A$は「$\sigma$が$\{1,\dots,k\}$を$A$の上へ写す」ことと同値である。

このような順列$\sigma$は、$\{1,\dots,k\}$から$A$への全単射と、$\{k+1,\dots,n\}$から$[n]\setminus A$への全単射の対によって定まり、逆にその対から$\sigma$が定まる。§D2.2 命題 3.1より前者は$k!$個、後者は$(n-k)!$個であるから、§D2.2 定理 2.3と§D2.2 命題 1.5より、条件を満たす順列は$k!\,(n-k)!$個である。▨

証明. 各$x\in X$に対し$S\cap(\{x\}\times Y)=\{x\}\times S_x$である。相異なる$x$に対するこれらの集合は互いに素であり、その合併は$S$に等しい。写像$y\mapsto(x,y)$は$S_x$から$\{x\}\times S_x$への全単射であるから、§D2.2 命題 1.5より$\lvert\{x\}\times S_x\rvert=\lvert S_x\rvert$である。$X$は有限であるから§D2.2 定理 2.1を適用して$\lvert S\rvert=\sum_{x\in X}\lvert\{x\}\times S_x\rvert=\sum_{x\in X}\lvert S_x\rvert$を得る。$Y$の側についても、$S\cap(X\times\{y\})=S^y\times\{y\}$として同じ議論を行えば$\lvert S\rvert=\sum_{y\in Y}\lvert S^y\rvert$を得る。▨

証明.$X$を$(2^{[n]},\subseteq)$の極大鎖の全体とする。命題 1.2 (2)より$X$は有限集合であり$\lvert X\rvert=n!$である。$\mathcal A\subseteq2^{[n]}$も有限集合である。$S=\{(\mathcal C,A)\in X\times\mathcal A:\ A\in\mathcal C\}$と置き、命題 2.1を適用する。

極大鎖ごとの計数.$\mathcal C\in X$を固定する。$S_{\mathcal C}=\{A\in\mathcal A:\ A\in\mathcal C\}$は$\mathcal C\cap\mathcal A$に等しい。$\mathcal C$は鎖であるからその二元は比較可能であり、$\mathcal A$は反鎖であるからその相異なる二元は比較不能である。ゆえに$\mathcal C\cap\mathcal A$が相異なる二元をもつことはなく、$\lvert S_{\mathcal C}\rvert\le1$である。したがって$\lvert S\rvert=\sum_{\mathcal C\in X}\lvert S_{\mathcal C}\rvert\le\lvert X\rvert=n!.$

反鎖の元ごとの計数.$A\in\mathcal A$を固定し、$k=\lvert A\rvert$と置く。$S^{A}=\{\mathcal C\in X:\ A\in\mathcal C\}$であるから、命題 1.2 (3)より$\lvert S^{A}\rvert=k!\,(n-k)!$である。したがって$\lvert S\rvert=\sum_{A\in\mathcal A}\lvert A\rvert!\,(n-\lvert A\rvert)!.$

二つの表示を比べると$\sum_{A\in\mathcal A}\lvert A\rvert!\,(n-\lvert A\rvert)!\le n!$である。両辺を正の数$n!$で割り、§D2.2 命題 3.1の公式$\binom{n}{k}=\frac{n!}{k!\,(n-k)!},\qquad\text{すなわち}\qquad\frac{k!\,(n-k)!}{n!}=\binom{n}{k}^{-1}$を用いると、主張の不等式を得る。▨

証明.$1\le k\le n$とすると、§D2.2 命題 3.1の公式より$\frac{\binom nk}{\binom{n}{k-1}}=\frac{n!\,(k-1)!\,(n-k+1)!}{k!\,(n-k)!\,n!}=\frac{n-k+1}{k}$である。分母$k$は正であるから、$\binom nk>\binom{n}{k-1}\iff k<\frac{n+1}{2},\qquad\binom nk=\binom{n}{k-1}\iff k=\frac{n+1}{2},\qquad\binom nk<\binom{n}{k-1}\iff k>\frac{n+1}{2}$が成り立つ。

$n$が偶数のとき.$n=2m$と書くと$(n+1)/2=m+\tfrac12$は整数ではない。したがって$1\le k\le m$では$\binom nk>\binom n{k-1}$、$m+1\le k\le n$では$\binom nk<\binom n{k-1}$である。ゆえに$\binom n0<\binom n1<\dots<\binom nm$かつ$\binom nm>\binom n{m+1}>\dots>\binom nn$であり、最大値は$k=m=n/2=\lfloor n/2\rfloor$でのみ達成される。

$n$が奇数のとき.$n=2m+1$と書くと$(n+1)/2=m+1$である。したがって$1\le k\le m$では$\binom nk>\binom n{k-1}$、$k=m+1$では$\binom n{m+1}=\binom nm$、$m+2\le k\le n$では$\binom nk<\binom n{k-1}$である。ゆえに最大値は$k=m$と$k=m+1$でのみ達成される。$m=(n-1)/2=\lfloor n/2\rfloor$かつ$m+1=(n+1)/2$であるから、主張の形になる。▨

証明.$N=\binom{n}{\lfloor n/2\rfloor}$と置く。補題 4.1より、各$A\in\mathcal A$について$\binom{n}{\lvert A\rvert}\le N$であり、両辺は正であるから$\binom{n}{\lvert A\rvert}^{-1}\ge N^{-1}$が成り立つ。これを$A\in\mathcal A$について加えると$\lvert\mathcal A\rvert\cdot N^{-1}\le\sum_{A\in\mathcal A}\binom{n}{\lvert A\rvert}^{-1}$となり、右辺は定理 3.1より$1$以下である。ゆえに$\lvert\mathcal A\rvert\le N$を得る。▨

証明.$S=\{(A,B)\in\mathcal F\times\nabla\mathcal F:\ A\subseteq B\}$と置き、命題 2.1を適用する。

$A\in\mathcal F$を固定する。$A\subseteq B$かつ$\lvert B\rvert=k+1$を満たす$B$は、$B=A\cup\{x\}$（$x\in[n]\setminus A$）の形のものに限り、相異なる$x$は相異なる$B$を与える。$\lvert[n]\setminus A\rvert=n-k$であるから、そのような$B$はちょうど$n-k$個ある。これらはいずれも$A\in\mathcal F$を含むので$\nabla\mathcal F$に属する。ゆえに$\lvert S_A\rvert=n-k$であり$\lvert S\rvert=\sum_{A\in\mathcal F}\lvert S_A\rvert=(n-k)\lvert\mathcal F\rvert.$

$B\in\nabla\mathcal F$を固定する。$S^{B}=\{A\in\mathcal F:\ A\subseteq B\}$は$B$の$k$元部分集合のうち$\mathcal F$に属するものの全体である。$B$の$k$元部分集合は$B$から一元を取り除いたものに限るから、ちょうど$k+1$個ある。ゆえに$\lvert S^{B}\rvert\le k+1$であり$\lvert S\rvert=\sum_{B\in\nabla\mathcal F}\lvert S^{B}\rvert\le(k+1)\lvert\nabla\mathcal F\rvert.$

二つを合わせて$(n-k)\lvert\mathcal F\rvert\le(k+1)\lvert\nabla\mathcal F\rvert$を得る。等号が成立することは、すべての$B\in\nabla\mathcal F$について$\lvert S^{B}\rvert=k+1$が成り立つこと、すなわち$B$の$k$元部分集合がすべて$\mathcal F$に属することと同値である。▨

証明. 非負整数$d$についての累積帰納法（§D2.1 命題 1.2）で、次の主張を示す。

$A\in\mathcal F$、$A'\in\binom{[n]}{k}$かつ$\lvert A'\setminus A\rvert=d$ならば$A'\in\mathcal F$である。

$d=0$のとき、$A'\subseteq A$かつ$\lvert A'\rvert=\lvert A\rvert=k$であるから$A'=A\in\mathcal F$である。

$d\ge1$とする。$\lvert A\rvert=\lvert A'\rvert$より$\lvert A\setminus A'\rvert=\lvert A'\setminus A\rvert=d\ge1$であるから、$y\in A'\setminus A$と$x\in A\setminus A'$を取ることができる。$A''=(A\setminus\{x\})\cup\{y\}$と置くと、$x\in A$かつ$y\notin A$より$\lvert A''\rvert=k$であり、$A\cap A''=A\setminus\{x\}$より$\lvert A\cap A''\rvert=k-1$である。仮定より$A''\in\mathcal F$である。

$x\notin A'$であるから$A'\setminus(A\setminus\{x\})=A'\setminus A$であり、$y\in A'$であるから$A'\setminus A''=(A'\setminus A)\setminus\{y\}$となって$\lvert A'\setminus A''\rvert=d-1$である。帰納法の仮定を$A''\in\mathcal F$と$A'$に適用すると$A'\in\mathcal F$を得る。

以上で主張が示された。$\mathcal F$は空でないので$A\in\mathcal F$を一つ取ることができ、任意の$A'\in\binom{[n]}{k}$に対し$\lvert A'\setminus A\rvert$は$0$以上$k$以下の整数であるから、主張より$A'\in\mathcal F$である。ゆえに$\mathcal F=\binom{[n]}{k}$である。▨

証明.$N=\binom{n}{\lfloor n/2\rfloor}$と置く。

十分性. 階層$\binom{[n]}{k}$は反鎖である。実際、濃度の等しい相異なる二集合は、いずれも他方を含まないから比較不能である。$n$が偶数のとき$\left\lvert\binom{[n]}{n/2}\right\rvert=\binom{n}{n/2}=N$である。$n$が奇数のとき、$\lfloor n/2\rfloor=(n-1)/2$であり、§D2.2 命題 3.1の公式から$\binom{n}{(n+1)/2}=\frac{n!}{\left(\frac{n+1}{2}\right)!\left(\frac{n-1}{2}\right)!}=\binom{n}{(n-1)/2}=N$であるから、いずれの階層も濃度$N$の反鎖である。

必要性.$\lvert\mathcal A\rvert=N$とする。系 4.2の証明に現れる二つの不等式を並べると$1\ge\sum_{A\in\mathcal A}\binom{n}{\lvert A\rvert}^{-1}\ge\lvert\mathcal A\rvert\cdot N^{-1}=1$であるから、両方が等号である。とくに右側の等号は、各$A\in\mathcal A$について$\binom{n}{\lvert A\rvert}^{-1}=N^{-1}$、すなわち$\binom{n}{\lvert A\rvert}=N$が成り立つことを意味する。補題 4.1の等号成立条件より、$n$が偶数ならばすべての$A\in\mathcal A$が$\lvert A\rvert=n/2$を満たし、$n$が奇数ならばすべての$A\in\mathcal A$が$\lvert A\rvert\in\{(n-1)/2,(n+1)/2\}$を満たす。

$n$が偶数の場合.$\mathcal A\subseteq\binom{[n]}{n/2}$であり、両者の濃度はともに$N$である。有限集合であるから$\mathcal A=\binom{[n]}{n/2}$を得る。

$n$が奇数の場合.$n=2m+1$と書く。$\lfloor n/2\rfloor=m$であり、上で見たとおり$\binom nm=\binom n{m+1}=N$である。$\mathcal A_1=\mathcal A\cap\binom{[n]}{m},\qquad\mathcal A_2=\mathcal A\cap\binom{[n]}{m+1}$と置くと、上で示したことから$\mathcal A=\mathcal A_1\cup\mathcal A_2$であり、二つは互いに素であるから§D2.2 定理 2.1より$\lvert\mathcal A\rvert=\lvert\mathcal A_1\rvert+\lvert\mathcal A_2\rvert$である。

$\nabla\mathcal A_1\cap\mathcal A_2=\varnothing$である。実際、$B$が両方に属するとすると、$A\subseteq B$を満たす$A\in\mathcal A_1$が存在し、$\lvert A\rvert=m<m+1=\lvert B\rvert$より$A\subsetneq B$である。$A$と$B$はともに$\mathcal A$に属するから、これは$\mathcal A$が反鎖であることに反する。

$\nabla\mathcal A_1$と$\mathcal A_2$はいずれも$\binom{[n]}{m+1}$に含まれ互いに素であるから$\lvert\nabla\mathcal A_1\rvert+\lvert\mathcal A_2\rvert\le\binom{n}{m+1}=N$である。また補題 5.1を$k=m$に対して適用すると、$n-k=(2m+1)-m=m+1=k+1$であるから$(m+1)\lvert\mathcal A_1\rvert\le(m+1)\lvert\nabla\mathcal A_1\rvert,\qquad\text{すなわち}\qquad\lvert\mathcal A_1\rvert\le\lvert\nabla\mathcal A_1\rvert$を得る。以上を合わせると$N=\lvert\mathcal A\rvert=\lvert\mathcal A_1\rvert+\lvert\mathcal A_2\rvert\le\lvert\nabla\mathcal A_1\rvert+\lvert\mathcal A_2\rvert\le N$であるから、二つの不等号はいずれも等号である。

$\mathcal A_1=\varnothing$の場合、$\lvert\mathcal A_2\rvert=N=\binom n{m+1}$であり$\mathcal A_2\subseteq\binom{[n]}{m+1}$であるから$\mathcal A=\mathcal A_2=\binom{[n]}{m+1}=\binom{[n]}{(n+1)/2}$である。

$\mathcal A_1\ne\varnothing$の場合、$\lvert\mathcal A_1\rvert=\lvert\nabla\mathcal A_1\rvert$が成り立つので、補題 5.1の等号成立条件より、$\nabla\mathcal A_1$のすべての元$B$について$B$の$m$元部分集合はすべて$\mathcal A_1$に属する。これを用いて$\mathcal A_1$が補題 5.2の仮定を満たすことを示す。$A\in\mathcal A_1$と$A'\in\binom{[n]}{m}$が$\lvert A\cap A'\rvert=m-1$を満たすとする。このとき$\lvert A\cup A'\rvert=\lvert A\rvert+\lvert A'\rvert-\lvert A\cap A'\rvert=m+m-(m-1)=m+1$であり、$B=A\cup A'$は$A\in\mathcal A_1$を含むから$B\in\nabla\mathcal A_1$である。$A'$は$B$の$m$元部分集合であるから$A'\in\mathcal A_1$である。

ゆえに補題 5.2より$\mathcal A_1=\binom{[n]}{m}$である。このとき$\binom{[n]}{m+1}$の任意の元$B$は$m$元部分集合をもち、それは$\mathcal A_1$に属するから$B\in\nabla\mathcal A_1$であり、$\nabla\mathcal A_1=\binom{[n]}{m+1}$となる。$\mathcal A_2$は$\binom{[n]}{m+1}$に含まれ$\nabla\mathcal A_1$と互いに素であるから$\mathcal A_2=\varnothing$であり、$\mathcal A=\mathcal A_1=\binom{[n]}{m}=\binom{[n]}{(n-1)/2}$を得る。▨