Erdős–Ko–Radoの定理

同義語：Erdős-Ko-Radoの定理Erdős–Ko–Rado theorem

概要

前提知識: 集合族, 二項係数, 置換

Erdős–Ko–Rado の定理（Erdős–Ko–Rado theorem）とは、$n\ge2k$ のとき、$n$ 元集合 $[n]=\{1,2,\dots,n\}$ の $k$ 元部分集合からなる族 $\mathcal F$ で、どの 2 つの元も共通の元をもつものについて
$$ |\mathcal F|\le\binom{n-1}{k-1} $$
が成り立つという定理である（Erdős・Ko・Rado、1961 年）。$1$ を含む $k$ 元部分集合をすべて集めた族は条件を満たし、ちょうど $\binom{n-1}{k-1}$ 個の元をもつので、この上界は最良である。さらに $n>2k$ なら、等号が成り立つのは族が「ある 1 点を含む $k$ 元部分集合の全体」（星）であるときに限る。
Spernerの定理と並ぶ極値集合論の基本定理であり、「交わる」という条件だけで族の大きさが全体 $\binom nk$ の $k/n$ 倍以下に抑えられることを述べている。この記事では、Katona による円順序を使った短い証明を与え、そこから $n>2k$ での等号の場合が星に限ることを導く。$n=2k$（$k\ge2$）では星以外にも最大の族がたくさんあること、$k< n<2k$ では上界そのものが成り立たないことを例で確かめる。

定義

$n\ge1$、$1\le k\le n$ を整数とし、$[n]:=\{1,\dots,n\}$ とおく。$[n]$ の $k$ 元部分集合の全体を $\binom{[n]}{k}$ と書く。その元の個数は二項係数 $\binom nk$ である。

交わる族と星

$[n]$ の部分集合の族 $\mathcal F$ が 交わる族（intersecting family）であるとは、任意の $A,B\in\mathcal F$ について $A\cap B\neq\emptyset$ が成り立つことをいう。$x\in[n]$ について
$$ \mathcal S_x:=\Bigl\{A\in\binom{[n]}{k}\Bigm| x\in A\Bigr\} $$
を $x$ を中心とする星（star）という。

星 $\mathcal S_x$ の 2 元はどちらも $x$ を含むので、$\mathcal S_x$ は交わる族である。$A\in\mathcal S_x$ は $A\setminus\{x\}$ という $[n]\setminus\{x\}$ の $(k-1)$ 元部分集合で決まるので、$|\mathcal S_x|=\binom{n-1}{k-1}$ である。

直感

$n=5$、$k=2$ とする。$\binom{[5]}{2}$ の 10 個の 2 元集合のうち、どの 2 つも交わるものをできるだけ多く選びたい。星 $\{12,13,14,15\}$（$ij$ で $\{i,j\}$ を表す）は 4 個である。三角形 $\{12,13,23\}$ も交わる族だが、これに 4 個目を加えると、その 2 元集合は $12,13,23$ のすべてと交わるために $\{1,2,3\}$ に含まれなければならず、加えられない。$4=\binom41$ が最大であることは、独立集合の記事の例で Petersen グラフの独立数として直接確かめられている。
一般の $n,k$ で一つひとつ調べるのは難しい。Katona の発想は、$[n]$ の元を円周上に並べ、円周上で連続する $k$ 個の元（弧）だけに目を向けることである。弧は $n$ 個しかなく、交わる弧は高々 $k$ 個しか選べないことが簡単に示せる。並べ方をすべて動かして平均すると、族全体の大きさの評価が得られる。

円順序と弧

$\mathbb Z/n\mathbb Z$ から $[n]$ への全単射 $\sigma$ を 円順序 という（$[n]$ の元を円周上の $n$ 個の位置 $0,1,\dots,n-1$ に 1 つずつ置く置き方）。$1\le k\le n-1$ と $s\in\mathbb Z/n\mathbb Z$ について
$$ I(s):=\{s,s+1,\dots,s+k-1\}\subset\mathbb Z/n\mathbb Z,\qquad A_\sigma(s):=\sigma\bigl(I(s)\bigr) $$
とおき、$A_\sigma(s)$ を $\sigma$ の 始点 $s$ の弧 という。円順序は $n!$ 個あり、各円順序の弧は $n$ 個ある。

$s\ne t$ なら位置の集合 $I(s)$ と $I(t)$ は異なるので、弧 $A_\sigma(s)$ と $A_\sigma(t)$ も異なる。位置 $s,t$ の 円周上の距離 を、$s-t$ を $\{0,1,\dots,n-1\}$ の代表 $r$ で表したときの $\min(r,n-r)$ と定める。

弧が交わる条件

$n\ge2k$ とする。始点 $s,t$ の弧が交わることと、$s,t$ の円周上の距離が $k-1$ 以下であることは同値である。

$\sigma$ は全単射なので、$I(s)\cap I(t)\ne\emptyset$ かどうかを見ればよい。$t=s+r$（$0\le r\le n-1$）とする。$r\le k-1$ なら $t\in I(s)\cap I(t)$ である。$n-r\le k-1$ なら $s=t+(n-r)\in I(t)\cap I(s)$ である。$k\le r\le n-k$ なら、$I(s)=\{s,\dots,s+k-1\}$ と $I(t)=\{s+r,\dots,s+r+k-1\}$ は、代表 $0,\dots,k-1$ と $r,\dots,r+k-1$（$r+k-1\le n-1$）が重ならないので交わらない。距離が $k-1$ 以下であることは、$r\le k-1$ または $n-r\le k-1$ と同じである。$\square$

円周上の Erdős–Ko–Rado の定理

$n\ge2k$、$k\ge1$ とし、$\sigma$ を円順序とする。$\sigma$ の弧からなる交わる族は高々 $k$ 個の元をもつ。さらに $n>2k$ で、ちょうど $k$ 個の元をもつ交わる族 $\mathcal B$ は、ある位置 $q$ を含む $k$ 個の弧 $A_\sigma(q-k+1),\dots,A_\sigma(q)$ の全体である。

$\mathcal B$ を空でない交わる族とし、平行移動して $A_\sigma(0)\in\mathcal B$ としてよい。$S:=\{s\mid A_\sigma(s)\in\mathcal B\}$ とおく。lem-ekr-arc-meet により、$S$ の元はすべて $0$ との距離が $k-1$ 以下なので、$S\subset\{-(k-1),\dots,k-1\}$ である。$1\le i\le k-1$ について、$i$ と $i-k$ の距離は $\min(k,n-k)=k$ なので、始点 $i$ と始点 $i-k$ の弧は交わらず、$S$ はこの 2 つのうち高々 1 つしか含まない。$\{-(k-1),\dots,k-1\}\setminus\{0\}$ はこの $k-1$ 組の対に分かれるので、$|S|\le1+(k-1)=k$ である。
$n>2k$ で $|S|=k$ とする。各対からちょうど 1 つが $S$ に属する。$2\le i\le k-1$ について、$i\in S$ なら $i-1\in S$ であることを示す。$i-1\notin S$ なら $i-1-k\in S$ だが、$i$ と $i-1-k$ の距離は $\min(k+1,n-k-1)$ で、$n\ge2k+1$ からこれは $k$ 以上である。よって 2 つの弧は交わらず矛盾する。したがって $S\cap\{1,\dots,k-1\}=\{1,\dots,m\}$（$0\le m\le k-1$）であり、残りの対からは負の側が選ばれて $S\cap\{-(k-1),\dots,-1\}=\{m+1-k,\dots,-1\}$ となる。すなわち $S=\{m-k+1,\dots,m\}$ であり、$q:=m$ とおけば $\mathcal B$ は位置 $q$ を含む $k$ 個の弧の全体である。$\square$

$n=2k$ では始点 $i$ と $i-1-k$ の距離が $k-1$ になり、後半の議論が使えない。実際、$n=6$、$k=3$ の円順序 $\sigma(j)=j+1$ では、3 個の弧 $\{1,2,3\},\{3,4,5\},\{5,6,1\}$ はどの 2 つも交わるが、3 つに共通な元はない。

Erdős–Ko–Rado の定理

$n\ge2k$、$k\ge1$ とし、$\mathcal F\subset\binom{[n]}{k}$ を交わる族とする。このとき
$$ |\mathcal F|\le\binom{n-1}{k-1} $$
が成り立ち、星 $\mathcal S_x$ が等号を与える。

円順序 $\sigma$ と $A\in\mathcal F$ の組で、$A$ が $\sigma$ の弧であるものの個数 $N$ を 2 通りに数える。
各 $\sigma$ について、$\mathcal F$ に属する $\sigma$ の弧の全体は $\sigma$ の弧からなる交わる族なので、lem-ekr-circle によりその個数は $k$ 以下である。円順序は $n!$ 個あるので $N\le k\cdot n!$ である。
一方、$A\in\mathcal F$ を 1 つ固める。$A$ が始点 $s$ の弧になる円順序は、位置 $I(s)$ に $A$ の元を並べる $k!$ 通りと、残りの位置に $[n]\setminus A$ の元を並べる $(n-k)!$ 通りで決まる。始点が異なれば弧の位置の集合が異なるので、これらは $s$ ごとに重ならない。よって $A$ を弧にもつ円順序はちょうど $n\cdot k!\,(n-k)!$ 個であり、$N=|\mathcal F|\cdot n\cdot k!\,(n-k)!$ である。
合わせると $|\mathcal F|\cdot n\cdot k!\,(n-k)!\le k\cdot n!$、すなわち
$$ |\mathcal F|\le\frac kn\cdot\frac{n!}{k!\,(n-k)!}=\frac kn\binom nk=\binom{n-1}{k-1} $$
を得る。$\square$

この証明は Katona（1972 年）による（Fra20 Theorem 3.1・Theorem 3.2 とその証明、pp. 6–8。KT17 Theorem 16.8、pp. 319–320 も同じ数え上げで証明している）。証明の形は、Spernerの定理の LYM 不等式の証明（極大鎖を数える）とよく似ている。極大鎖の代わりに円順序の弧を数え、「鎖は Sperner 族の元を高々 1 つ含む」の代わりに lem-ekr-circle を使っている。

等号の場合

$n>2k$、$k\ge1$ とし、$\mathcal F\subset\binom{[n]}{k}$ を $|\mathcal F|=\binom{n-1}{k-1}$ をみたす交わる族とする。このとき、ある $x\in[n]$ について $\mathcal F=\mathcal S_x$ である。

要点：等号なら各円順序で $\mathcal F$ に属する弧はある 1 点 $p(\sigma)$ を含む $k$ 個の弧の全体であり、その点 $p(\sigma)$ は円順序の隣り合う 2 元を入れ替えても（$p(\sigma)$ 自身を動かさない限り）変わらない。これを使って、星 $\mathcal S_{p}$ のすべての元が $\mathcal F$ に属することを示す。

詳細

段 1（各円順序の形）．$k=1$ なら交わる族は 1 元以下で、$\binom{n-1}{0}=1$ だから $\mathcal F=\{\{x\}\}=\mathcal S_x$ である。以下 $k\ge2$ とする。prf-ekr-main の数え上げで等号が成り立つので、すべての円順序 $\sigma$ について、$\mathcal F$ に属する $\sigma$ の弧はちょうど $k$ 個である。lem-ekr-circle により、それはある位置を含む $k$ 個の弧の全体である。その位置の元を $p(\sigma)$ と書く。位置 $q$ を含む弧の始点の集合 $J(q):=\{q-k+1,\dots,q\}$ について、$q\ne q'$ のとき $|J(q)\cap J(q')|=\max(0,k-d)$（$d$ は $q,q'$ の距離。$n>2k$ なので反対側からの重なりはない）である。とくに $q\ne q'$ なら $J(q)\ne J(q')$ なので、位置 $q$ は $J(q)$ で決まり、$p(\sigma)$ は $\sigma$ で決まる。

段 2（入れ替えで $p$ は変わらない）．$\sigma$ について $p(\sigma)$ の位置を $0$ とし、$1\le t\le n-2$ について、位置 $t$ と $t+1$ の元を入れ替えた円順序を $\sigma'$ とする（位置 $0$ は動かない）。弧のうち、$t$ と $t+1$ の一方だけを含むもの、すなわち始点 $t-k+1$ と始点 $t+1$ の弧だけが集合として変わり、ほかの弧は $\sigma$ と $\sigma'$ で同じ集合である。$\sigma'$ の $\mathcal F$ に属する弧の位置を $r$ とし、$r\ne0$ と仮定する。始点の集合 $J(0)$ は、差が $k$ の 2 つの始点 $t-k+1,t+1$ の高々 1 つしか含まないので、$J(0)$ の始点のうち少なくとも $k-1$ 個の弧は変わらず、$\mathcal F$ に属する $\sigma'$ の弧として $J(r)$ に入る。よって $|J(0)\cap J(r)|\ge k-1\ge1$ であり、距離は $1$、すなわち $r=\pm1$ である。$r=1$ とする。始点 $-(k-1)$ の弧は $J(0)$ にあって $J(1)$ にないので、変わらないなら $\mathcal F$ に属する $\sigma'$ の弧なのに位置 $1$ を含まず矛盾する。よってこの弧は変わる。始点 $1$ の弧は $J(1)$ にあって $J(0)$ にないので、変わらないなら $\sigma$ の弧として $\mathcal F$ に属するのに位置 $0$ を含まず矛盾する。よってこれも変わる。変わる弧の始点は $t-k+1$ と $t+1$ なので $\{t-k+1,t+1\}=\{-(k-1),1\}$ である。$t-k+1=-(k-1)$ なら $t=0$ で $t\ge1$ に反する。$t+1\equiv-(k-1)$ かつ $t-k+1\equiv1$ なら $t\equiv k$ で $k+1\equiv-(k-1)$、すなわち $n$ が $2k$ を割り切ることになり、$n>2k$ に反する。$r=-1$ のときも同様に、始点 $0$ と始点 $-k$ の弧が変わることになり、$\{t-k+1,t+1\}=\{0,-k\}$ から $t\equiv-1$（$t=n-1$ で、位置 $0$ を動かす入れ替え）か、$n$ が $2k$ を割り切ることになって矛盾する。よって $r=0$、すなわち $p(\sigma')=p(\sigma)$ である。

段 3（星を含む）．$p:=p(\sigma)$ を 1 つの円順序 $\sigma$ について定める。位置 $1,\dots,n-1$ の上の隣り合う入れ替えは、位置 $0$ に $p$ を置いたままの任意の並べ替えを生成するので、段 2 から、$p$ を位置 $0$ に置く円順序 $\tau$ はすべて $p(\tau)=p$ をみたす。$B\in\mathcal S_p$ を任意にとり、$B\setminus\{p\}$ の元を位置 $1,\dots,k-1$ に置いた $\tau$ をとれば、$B=A_\tau(0)$ は位置 $0$ を含む弧なので $B\in\mathcal F$ である。よって $\mathcal S_p\subset\mathcal F$ であり、大きさが等しいので $\mathcal F=\mathcal S_p$ である。$\square$

等号の場合は、星でない交わる族の大きさの最大値を与える Hilton–Milner の定理からも従う。$n>2k\ge4$ のとき、星でない交わる族 $\mathcal H\subset\binom{[n]}{k}$ は
$$ |\mathcal H|\le\binom{n-1}{k-1}-\binom{n-k-1}{k-1}+1 $$
をみたし、右辺は $\binom{n-1}{k-1}$ より小さい（Fra20 Example 5.1・Theorem 5.2、p. 11。この記事では証明しない）。右辺は、$1$ を含み $\{2,\dots,k+1\}$ と交わる $k$ 元集合の全体に $\{2,\dots,k+1\}$ を加えた族の大きさである。

$n\le 2k$ の場合

$n=2k$ の場合の最大の族

$n=2k$、$k\ge1$ とする。$\binom{[2k]}{k}$ の元は、補集合どうしの $\frac12\binom{2k}{k}=\binom{2k-1}{k-1}$ 組の対に分かれる。交わる族は各対から高々 1 つしか含まない。逆に、各対から 1 つずつ選んだ族はどれも交わる族である。とくに大きさ $\binom{2k-1}{k-1}$ の交わる族はちょうど $2^{\binom{2k-1}{k-1}}$ 個ある。

$A\in\binom{[2k]}{k}$ の補集合 $[2k]\setminus A$ も $k$ 元集合で、$A$ と交わらないので、交わる族は 1 組の対の両方を含まない。逆に $A,B$ が $k$ 元集合で $A\cap B=\emptyset$ なら $|A\cup B|=2k$ より $B=[2k]\setminus A$ である。各対から 1 つずつ選んだ族の相異なる 2 元は補集合の関係にないので交わる。$\binom{2k}k=\frac{2k}{k}\binom{2k-1}{k-1}=2\binom{2k-1}{k-1}$ だから対は $\binom{2k-1}{k-1}$ 組あり、選び方は対ごとに 2 通りなので、個数は $2^{\binom{2k-1}{k-1}}$ である。$\square$

$k\ge2$ なら星は $2k$ 個しかなく、$2^{\binom{2k-1}{k-1}}>2k$ なので、$n=2k$ では星でない最大の族がある。この命題は $n=2k$ の場合の thm-ekr-main の別証明にもなっている。
$k< n<2k$ のときは、どの 2 つの $k$ 元部分集合も $|A|+|B|=2k>n$ から交わるので、$\binom{[n]}{k}$ 全体が交わる族であり、
$$ \binom nk=\frac nk\binom{n-1}{k-1}>\binom{n-1}{k-1} $$
となって thm-ekr-main の不等式は成り立たない。$n=k$ では両辺とも $1$ である。

例と反例

小さい場合

$n=4$、$k=2$：大きさ $\binom31=3$ の交わる族は prop-ekr-half により $2^3=8$ 個あり、星 $\mathcal S_1,\dots,\mathcal S_4$ の 4 個と、三角形 $\{12,13,23\}$ のような $\binom{T}{2}$（$T$ は 3 元集合）の 4 個である。
$n=6$、$k=3$：最大の大きさは $\binom52=10$ で、最大の族は $2^{10}=1024$ 個あるが、星は 6 個だけである。
$n=7$、$k=3$：$n>2k$ なので、大きさ $\binom62=15$ の交わる族は 7 個の星だけである。Fano平面の 7 本の直線は、どの 2 本も 1 点で交わる 3 元集合の族だが、大きさは 7 で最大ではない。

次の表は、各行で仮定を 1 つだけ外したときに結論が成り立たなくなる例である。

外す条件	反例	成り立たなくなること
$n\ge2k$（不等式）	$n=3$、$k=2$、$\binom{[3]}{2}$ の全体	$\lvert\mathcal F\rvert\le\binom{n-1}{k-1}=2$
$n>2k$（等号の場合）	$n=4$、$k=2$、$\{12,13,23\}$	最大の族が星に限ること
元の大きさがすべて $k$ であること（$k=2$ で、大きさ $2$ 以下を許す）	$n\ge4$、$1$ を含む大きさ $1$ 以上 $2$ 以下の集合の全体	$\lvert\mathcal F\rvert\le\binom{n-1}{1}$
lem-ekr-circle の $n\ge2k$	$n=5$、$k=3$ の 5 個の弧	交わる弧が $k$ 個以下であること

反例の確かめ

1 行目は上の節のとおり。2 行目は ex-ekr-small の 1 である。3 行目の族は $\{1\}$ と $\{1,j\}$（$2\le j\le n$）からなり、すべて $1$ を含むので交わる族で、大きさは $n>n-1$ である。大きさを混ぜると星の大きさの評価は崩れるが、一般の部分集合の交わる族については、補集合の対を考える prop-ekr-half と同じ議論で $|\mathcal F|\le2^{n-1}$ が成り立ち、$1$ を含む部分集合の全体が等号を与える。4 行目では、$5$ 個の 3 元の弧はどの 2 つも $3+3>5$ から交わる。

補足

Kneser グラフ：$\binom{[n]}{k}$ を頂点とし、交わらない 2 元を辺で結んだグラフを Kneserグラフという。交わる族はその独立集合なので、thm-ekr-main は $n\ge2k$ での独立数が $\binom{n-1}{k-1}$ であることと同じである。$n=5$、$k=2$ が Petersen グラフである（独立集合）。彩色数については Kneser予想を参照。
影による証明：Kruskal–Katonaの定理を補集合の族に当てても thm-ekr-main が出る（Daykin による。Fra20 p. 7）。その証明は Kruskal–Katonaの定理の記事にある。
平均の議論：prf-ekr-main は、無作為に選んだ円順序の弧のうち $\mathcal F$ に属するものの個数の期待値を 2 通りに計算したものと読める（Fra20 Lemma 1.1）。