2014/11/01

Erdos-Ko-Radoの定理

分野: 場合の数  レベル: マニアック

Erdos-Ko-Radoの定理:$n$ 個の要素からなる集合 $\{1,2,\cdots,n\}$ から要素数が $k$ の部分集合たちを以下の条件を満たすようにできるだけたくさん選びたい。
条件:選んだ部分集合のどの二つを選んでも共通元が存在する。
$n\geq 2k$ のとき,選べる部分集合の限界 $N$ は,$N={}_{n-1}C_{k-1}$ 個である。

組み合わせの有名な定理です。証明は数学オリンピックの練習問題としては難し目ですが,非常にエレガントです。

注:本当は $\mathrm{Erd\ddot{o}s}$ ですが表記の都合上Erdosと書かせていただきますm(__)m

Erdos-Ko-Radoの定理の具体例

一般形では分かりにくいので様子をつかむために $n=4,\:k=2$ の場合で実験してみます。
$\{1,2,3,4\}$ という集合の部分集合を条件を満たすようにとってきます。
$\{1,2\},\{1,3\},\{1,4\}$ という三つの部分集合はどの二つを選んでも共通元 $1$ を含むので条件を満たしています。しかし,要素数が $2$ の部分集合を $4$ つ集めてくると必ず共通元を持たない二つの組ができてしまいます。
よって,選べる集合の限界は $3$ であり,確かに${}_{n-1}C_{k-1}={}_3C_{1}$ と一致しています!

また,$n <2k$ のときは,要素数が $k$ の部分集合をどのようにとってきてもそれらは共通元を持つので,全部持ってこれます。つまらない例です。このとき限界 $N$ は${}_{n}C_{k}$ となります。

共通元を持つ部分集合の構成

まず,$N\geq {}_{n-1}C_{k-1}$ であることは簡単に証明できます。実際に${}_{n-1}C_{k-1}$ 個の条件を満たす部分集合を持ってくればよいのです。どのように持って来ればよいか,鋭い方なら上記の具体例から推察できるはずです。

証明

選ぶ全ての部分集合に $1$ が含まれていれば自動的に条件は満たされる。
よって,$\{2,3,\cdots, n\}$ から要素数 $k-1$ の部分集合を全て選び(選び方は${}_{n-1}C_{k-1}$ 通り)それに $1$ を追加したものたちを考えればよい。

Erdos-Ko-Radoの定理の証明

$N\leq {}_{n-1}C_{k-1}$ を示すのが難しいです。どう頑張っても${}_{n-1}C_{k-1}$ 個までしか選べないことを言わなくてはなりません。1972年,Katonaによる証明です。

方針:証明は二段階に分かれています。第一段階として補題を示し,第二段階で二通りの方法で数える方法「double counting」を用います。

補題:$n$ 個の要素を円周上に等間隔に並べる。そこから連続する長さ $k$ の区間をいくつか選ぶ。「選んだ区間たちからどの二つを選んでも共通元を持つ」という条件を満たすようにするとき,選べる区間の数は $k$ 個以下である。

補題の証明

(補題の証明)
選んだ一つの区間の数字を。 $a_1,a_2,\cdots, a_k$ とする。他の選んだ区間はその区間をまたぐ必要があり,($1\leq i\leq k-1$ なる $i$ が存在して)$a_i$ と $a_{i+1}$ の間に境界がないといけない。
$a_i$ と $a_{i+1}$ の間を境界とする長さ $k$ の区間は二つあるが,$n\geq 2k$ よりそれらは共通元を持たないのでどちらか一つしか選べない。よって,最初に選んだ区間以外に選べるのは最大で $k-1$ 個なので全部で選べる区間の数は $k$ 個以下。

いよいよ本題です!条件を満たすように部分集合を $N$ 個選んできたとき,$N$ が${}_{n-1}C_{k-1}$ 以下であることを証明します。

定理の証明

「${1,2,\cdots, n}$ の円周上への並べ方」と「選んだ部分集合でその円周のとある区間に対応しているもの」のペア $P$ がいくつあるかを二通りの方法で数える。

erdoskoradoの証明

(例えば,$n=4,k=2$ で部分集合の中で $\{1,2\}$ と $\{2,3\}$ を選んだとき,上記のペアは図の赤丸と青丸に対応している。この丸の数を二通りの方法で数える。)

・「円順列それぞれに対してペアの数を数える」
まず,円周上への並べ方は全部で$(n-1)!$ 通り。補題により一つの並べ方に対して選べる区間の数は最大で $k$ 個なので,ペア $P$ の数は$(n-1)!k\:$以下。

・「赤丸と青丸を別々に数える」:
選んだ部分集合は $N$ 個あり。一つの部分集合に対して,それがとある区間となるような円周上への並べ方は全部で $k!(n-k)!$ 通りである。よって,ペア $P$ の数は $k!(n-k)!N$

以上から,$k!(n-k)!N\leq (n-1)!k$ となる。これを変形すると,$N\leq {}_{n-1}C_{k-1}$ を得る。

Erd$\ddot{o}$s, Ko, Radoはそれぞれ別の人物です。
分野: 場合の数  レベル: マニアック