Double Counting による Erdős–Ko–Rado 定理の証明 -

この記事は「好きな証明」アドベントカレンダー $3$ 日目の記事です．*1

何かを数えるとき，数え間違いを防ぐために，複数の方法で数えてみるというテクニックがありますよね．数学でもこれに似た手法が使われることがあり，同じ対象を $2$ 通りの方法で数えることにより，その数を通じた関係式を導く技法を Double Counting と呼びます．

たとえば，簡単な例として，非負の整数 $n$ に対して

$\displaystyle\sum_{k = 0}^n \binom{n}{k} = 2^n$

という等式を示してみましょう．ここで， $\binom{n}{k}$ は ${}_nC_k$ とも書かれる二項係数で，「 $n$ 個の異なる物から $k$ 個を選ぶ選び方の総数」に等しい値です．すると左辺は，その場合の数を，あり得る範囲のすべての $k$ に関して足し合わせたものになっています． $k$ の値が違えば同じ組合せが選ばれることも無いので，「 $n$ 個の異なる物からいくつかを選ぶ選び方の総数」を漏れなくダブりなく数えた式になっています．一方右辺は，「 $n$ 個の物それぞれに関して選ぶか選ばないか（ $2$ 通り）を決めることと，選ぶ物の組合せを決めることは同じである」という視点で，同じ場合の数を漏れなくダブりなく数えた式です．したがって，等式の両辺は，同じ対象を異なる方法で数えた式であるので，その値は等しいということが言えます．

では，もう少し非自明な主張を導いてみましょう． $n$ 人の生徒が居るクラスの中で， $k~(\le n/2)$ 人のチームをいくつか作りたいという状況を考えます．ただし，任意に $2$ つのチームを選んだときに，架け橋となるような，両方に属する生徒が必ず $1$ 人は居るようにしたいとします．このとき，最大でいくつのチームを作ることができるでしょうか？
たとえば，どのチームにも属するような生徒を $1$ 人固定して，残りの $(n-1)$ 人から $(k-1)$ 人を選ぶすべての組合せでチームを作ることを考えると， $\binom{n-1}{k-1}$ 個のチームを作ることができます．もっと多くのチームを作る方法はあるでしょうか？実は，そのような方法は存在しません．

定理 (Erdős–Ko–Rado)*2 正の整数 $n, k$ が $k \le n/2$ を満たすとし， $S$ を要素数 $n$ の集合とする． $\mathcal{F}$ は $S$ の部分集合族 $(\,X \in \mathcal{F} \implies X \subseteq S\,)$ であって，以下の性質をともに満たすとする．

各 $X \in \mathcal{F}$ の要素数は $k$ である． $(\,X \in \mathcal{F} \implies |X| = k\,)$
任意の $X, Y \in \mathcal{F}$ の交わりは空でない． $(\,X, Y \in \mathcal{F} \implies X \cap Y \neq \emptyset\,)$

このとき， $|\mathcal{F}| \le \displaystyle\binom{n-1}{k-1} = \frac{(n-1)!}{(n-k)!(k-1)!}$ が成り立つ．

証明 $S$ の要素を円形に並べた円順列は $(n-1)!$ 通りあり（回転して一致するものは同一視します），各円順列では， $(*)$ 「連続する $k$ 個の要素からなる $S$ の部分集合」が $n$ 通り（どちら回りに見るかを固定すると，始点の選び方が $n$ 通り）あります．以下では，あり得る円順列をすべて動かしたときに， $\mathcal{F}$ の要素が $(*)$ として出現する回数の総数を Double Counting することで，定理の主張を示します．

まず，各 $X \in \mathcal{F}$ を固定したときに， $X$ が何回出現するかを考えてみましょう． $X$ の要素が連続していてほしいので，これらをひとまとめにしたブロックと，残りの $(n - k)$ 個の要素で円順列を作ってみます．並べるものが $(n - k + 1)$ 個なので，その総数は $(n - k)!$ 通りです．ブロックの中で $X$ の要素はどういう順番で並んでいてもよいので，それぞれに関して $k!$ 通りずつ可能性があり，全体では $(n - k)!k!$ 通りの円順列で $X$ が $(*)$ として出現することがわかります．これは $\mathcal{F}$ のどの要素でも全く同じことなので，総数は $|\mathcal{F}| \cdot (n - k)!k!$ となります．

次に，各円順列を固定したときに， $(*)$ のうち $\mathcal{F}$ の要素がどれぐらい存在できるかを考えてみましょう．定理の $2$ つ目の条件から，もしある $X \in \mathcal{F}$ が $(*)$ として出現しているなら，他の $\mathcal{F}$ の要素はそこからどちらかの向きに高々 $(k - 1)$ 個分ずらした部分にしか $(*)$ として存在できません．あり得る候補として， $X$ からそれぞれの向きに $i \in [k - 1]$ 個分ずらした $(*)$ をそれぞれ $Y_i, Z_i$ と書くことにしましょう．このとき，もし $Y_i \in \mathcal{F}$ であったとすると， $Z_{k-i}$ はそこからちょうど $k$ 個分ずれた位置にあり，逆向きにも $n - k~(\ge k)$ 個分ずれているので， $Y_i \cap Z_{k-i} = \emptyset$ が成り立ちます．すなわち，各 $i$ について， $Y_i$ と $Z_{k-i}$ の高々一方しか $\mathcal{F}$ に属せないため， $(*)$ のうち $\mathcal{F}$ の要素となっているものは， $X$ を含めて高々 $k$ 個しか無いことがわかります．これはどの円順列でも全く同じことで，あり得る円順列は $(n-1)!$ 通りであったので，総数は高々 $(n-1)!k$ であることがわかります．

最後に，上の $2$ つの段落で Double Counting した対象は同じ（あり得る円順列をすべて動かしたときに， $\mathcal{F}$ の要素が $(*)$ として出現する回数の総数）であったので，

$\displaystyle|\mathcal{F}| \cdot (n - k)!k! \le (n - 1)! k$

という関係が得られ，これを変形すると

$\displaystyle|\mathcal{F}| \le \frac{(n - 1)!}{(n - k)!(k - 1)!} = \binom{n - 1}{k - 1}$

となり，定理の主張が示せました．(Q.E.D.)

本証明は，Katona (1972) による論文*3を参考にしています．

*1:この記事を書くために Hatena Blog を始めました．今後記事が増えるかどうかは未定です．

*2:P. Erdős, Chao Ko, R. Rado: Intersection theorem for system of finite sets. Quarterly Journal of Mathematics, Oxford Series, 12 (1961), pp. 313–320. (DOI: 10.1093/qmath/12.1.313)

*3:G. O. H. Katona: A simple proof of the Erdős–Chao Ko–Rado theorem. Journal of Combinatorial Theory, Series B, 13 (1972), pp. 183–184. (DOI: 10.1016/0095-8956(72)90054-8)