Kruskal–Katonaの定理

二項係数の和の公式 $\sum_{i=0}^{k-1}\binom{a-k+i}{i}=\binom{a}{k-1}$（$a\ge k$。$i$ についての帰納法と Pascal の公式で示せる）を使う。

一意性：上の形の表示があるとする。$a_i\le a_k-(k-i)$ なので、 $$ \sum_{i=s}^{k-1}\binom{a_i}{i}\le\sum_{i=1}^{k-1}\binom{a_k-k+i}{i}=\binom{a_k}{k-1}-1 $$ である。よって $\binom{a_k}k\le m<\binom{a_k}k+\binom{a_k}{k-1}=\binom{a_k+1}{k}$ となり、$a_k$ は $\binom ak\le m$ をみたす最大の $a$ に決まる。残り $r:=m-\binom{a_k}{k}$ が $0$ なら $s=k$ であり、$r\ge1$ なら $k\ge2$ で、$r=\sum_{i=s}^{k-1}\binom{a_i}{i}$ は $k-1$ についての同じ形の表示だから、$k$ についての帰納法で残りの $a_i$ も決まる。

存在：$a$ を $\binom ak\le m$ をみたす最大の整数とする（$\binom kk=1\le m$ なので $a\ge k$）。$r:=m-\binom ak<\binom{a+1}k-\binom ak=\binom a{k-1}$ である。$r=0$ なら終わる。$k=1$ なら $\binom a1=a\le m< a+1$ より $r=0$ である。$r\ge1$、$k\ge2$ なら、帰納法により $r=\sum_{i=s}^{k-1}\binom{a_i}{i}$ と書け、$\binom{a_{k-1}}{k-1}\le r<\binom{a}{k-1}$ から $a_{k-1}< a$ である。$\square$

$m=0$ なら両辺とも空である。$m\ge1$ とし、$k$ についての帰納法で示す。$k=1$ なら $\mathcal C_1(m)=\{\{1\},\dots,\{m\}\}$ の影は $\{\emptyset\}=\mathcal C_0(1)$ で、$\kappa_1(m)=\binom m0=1$ である。

$k\ge2$ とし、$a:=a_k$、$r:=m-\binom ak$ とおく（$0\le r<\binom a{k-1}$）。余辞書式順序では $\binom{[a]}{k}$ のすべての元のあとに、最大元が $a+1$ の集合が残りの部分の余辞書式順序で並ぶ。よって、$0\le t\le\binom{a}{k-1}$ について $$ \mathcal C_k\Bigl(\binom ak+t\Bigr)=\binom{[a]}{k}\cup\bigl\{B\cup\{a+1\}\bigm|B\in\mathcal C_{k-1}(t)\bigr\},\qquad\mathcal C_{k-1}(t)\subset\binom{[a]}{k-1} $$ である（この式を (1) と呼ぶ。$k-1$ でも同じ式が成り立つ）。$t=r$ として影をとる。$\binom{[a]}k$ の影は $\binom{[a]}{k-1}$ である（$a\ge k$）。$B\cup\{a+1\}$ の元を 1 つ除くと、$B$ そのもの（$\binom{[a]}{k-1}$ に入る）か、$B'\cup\{a+1\}$（$B'\in\partial\{B\}$）である。よって $$ \partial\mathcal C_k(m)=\binom{[a]}{k-1}\cup\bigl\{B'\cup\{a+1\}\bigm|B'\in\partial\mathcal C_{k-1}(r)\bigr\} $$ である。帰納法の仮定から $\partial\mathcal C_{k-1}(r)=\mathcal C_{k-2}(\kappa_{k-1}(r))$ であり、これは $\binom{[a]}{k-1}$ に含まれる族の影なので $\binom{[a]}{k-2}$ に含まれ、$\kappa_{k-1}(r)\le\binom a{k-2}$ である。(1) を $k-1$ について $t=\kappa_{k-1}(r)$ で使うと、右辺は $\mathcal C_{k-1}\bigl(\binom a{k-1}+\kappa_{k-1}(r)\bigr)$ である。lem-kk-cascade の表示は $r$ の $k-1$ についての表示に $\binom ak$ を加えたものなので、$\kappa_k(m)=\binom a{k-1}+\kappa_{k-1}(r)$ であり、主張を得る。$\square$

段 1（$B$ の形）．$B=A'\setminus\{x\}$、$A'\in\mathcal F'$ とする。$A'\in\mathcal F$ なら $B\in\partial\mathcal F$ となるので $A'\notin\mathcal F$ であり、$A'=(A\setminus V)\cup U$ をみたす $A\in\mathcal F$（$V\subset A$、$A\cap U=\emptyset$）がある。$x\in U$ と仮定する。仮定により $v\in V$ があって $\mathcal F$ は $(U\setminus\{x\},V\setminus\{v\})$-圧縮済みである。$A\supset V\setminus\{v\}$、$A\cap(U\setminus\{x\})=\emptyset$ なので $(A\setminus(V\setminus\{v\}))\cup(U\setminus\{x\})=B\cup\{v\}$ が $\mathcal F$ に属し、$B\in\partial\mathcal F$ となって矛盾する。よって $x\notin U$ であり、$x\in A'$ から $x\notin V$ でもある。したがって $U\subset B$、$B\cap V=\emptyset$ であり、$C:=(B\setminus U)\cup V=A\setminus\{x\}\in\partial\mathcal F$ である。

段 2（$C\notin\partial\mathcal F'$）．$C\subset D$、$D\in\mathcal F'$ と仮定し、$D=C\cup\{z\}$ とする。$V\subset C\subset D$ なので、$D$ は動かされた集合ではなく（動かされた集合は $V$ と交わらない）、$D\in\mathcal F$ であり、$D\in\mathcal F'$ から $C_{UV}(D)\in\mathcal F$ である。$C\cap U=\emptyset$ に注意する。$z\notin U$ なら $D\cap U=\emptyset$ で、$C_{UV}(D)=(D\setminus V)\cup U=B\cup\{z\}\in\mathcal F$ となり $B\in\partial\mathcal F$ に反する。$z\in U$ なら、仮定により $v\in V$ があって $\mathcal F$ は $(U\setminus\{z\},V\setminus\{v\})$-圧縮済みである。$D\supset V\setminus\{v\}$、$D\cap(U\setminus\{z\})=\emptyset$ なので $(D\setminus(V\setminus\{v\}))\cup(U\setminus\{z\})=B\cup\{v\}\in\mathcal F$ となり、やはり $B\in\partial\mathcal F$ に反する。$\square$

段 1（シフト）．$k=1$ なら $|\partial\mathcal F|=1=\binom x0$ である。$k\ge2$ とする。$U=\{1\}$、$V=\{j\}$（$j\ge2$）の圧縮は lem-kk-compression の仮定を自明にみたすので影を増やさず、重み $w$ を減らす。よってこれを繰り返して、大きさが同じで影が大きくない族で、すべての $j\ge2$ について $(\{1\},\{j\})$-圧縮済みのものに替えてよい。以下 $\mathcal F$ をそのような族とする。

段 2（分解）．$\mathcal F_0:=\{A\in\mathcal F\mid1\notin A\}$、$\mathcal F_1:=\{A\setminus\{1\}\mid1\in A\in\mathcal F\}$ とおく。$\mathcal F_1$ は $1$ を含まない $(k-1)$ 元集合の族で、$m=|\mathcal F_0|+|\mathcal F_1|$ である。$\partial\mathcal F$ は、$1$ を含まない部分として $\mathcal F_1$ を、$1$ を含む部分として $\{B\cup\{1\}\mid B\in\partial\mathcal F_1\}$ を含むので、$|\partial\mathcal F|\ge|\mathcal F_1|+|\partial\mathcal F_1|$ である。また $A\in\mathcal F_0$、$j\in A$ なら、圧縮済みであることから $(A\setminus\{j\})\cup\{1\}\in\mathcal F$ なので $A\setminus\{j\}\in\mathcal F_1$ である。すなわち $\partial\mathcal F_0\subset\mathcal F_1$ である。

段 3（$|\mathcal F_1|\ge\binom{x-1}{k-1}$）．$\mathcal F_0=\emptyset$ なら $|\mathcal F_1|=\binom xk=\binom{x-1}{k-1}+\binom{x-1}{k}\ge\binom{x-1}{k-1}$ である（$x-1\ge k-1$ より $\binom{x-1}k\ge0$）。$\mathcal F_0\ne\emptyset$ とし、$|\mathcal F_1|<\binom{x-1}{k-1}$ と仮定する。$|\mathcal F_0|>\binom xk-\binom{x-1}{k-1}=\binom{x-1}{k}$ である。$\emptyset\ne\partial\mathcal F_0\subset\mathcal F_1$ なので $|\mathcal F_0|< m$ である。$|\mathcal F_0|=\binom yk$（$y\ge k$）と書くと、$\binom{\cdot}{k}$ の $[k-1,\infty)$ での単調性から $y>x-1$ である。$m$ についての帰納法の仮定から $|\mathcal F_1|\ge|\partial\mathcal F_0|\ge\binom y{k-1}>\binom{x-1}{k-1}$ となり矛盾する。

段 4（まとめ）．$|\mathcal F_1|=\binom z{k-1}$（$z\ge k-1$）と書くと、段 3 と単調性から $z\ge x-1$ である。$k$ についての帰納法の仮定から $|\partial\mathcal F_1|\ge\binom z{k-2}\ge\binom{x-1}{k-2}$ である。段 2 と合わせて $|\partial\mathcal F|\ge\binom{x-1}{k-1}+\binom{x-1}{k-2}=\binom x{k-1}$ を得る。$\square$