8.5. 個別代表系

Hall の結婚定理 (定理 8.3.4) のグラフを使わない表現を二つ紹介する。組合せ論以外の分野で Hall の結婚定理を使うときは、これらの表現が用いられることが多い。一つ目の表現は次の通りである:

定理 8.5.1

[SDR の存在] \(A_{1},A_{2},\ldots,A_{n}\) を \(n\) 個の集合とする。全ての \(p\in\left\{ 0,1,\ldots,n\right\} \) に対して、これらの集合から任意に取った \(p\) 個の集合の和集合が \(p\) 個以上の要素を持つとする。言い換えれば、全ての \(p\in\left\{ 0,1,\ldots,n\right\} \) に対して次の条件が成り立つと仮定する:

\[ \begin{aligned} \forall i_{1} \forall i_{2} \ldots \forall i_{p} \in \left\{1,2,\ldots,n\right\}, \quad &1\leq i_{1} < i_{2} < \cdots < i_{p}\leq n \\ &\qquad \Longrightarrow \left\vert A_{i_{1}}\cup A_{i_{2}}\cup\cdots\cup A_{i_{p}}\right\vert \geq p \end{aligned} \]

このとき、次の条件を満たす \(n\) 個の相異なる要素 \(a_{1}\), \(a_{2}\), ..., \(a_{n}\) が存在する:

\[ a_{1}\in A_{1},\qquad a_{2}\in A_{2},\qquad \ldots,\qquad a_{n}\in A_{n} \]

Remark 8.5.2

定理 8.5.1 の条件を満たす \(n\) 個の異なる要素からなる列 \(\left( a_{1},a_{2},\ldots,a_{n}\right) \) を、\(n\) 個の集合 \(A_{1},A_{2},\ldots,A_{n}\) の個別代表系 (system of distinct representatives) と呼ぶ。個別代表系は SDR とも呼ばれる。

例 8.5.3

通常のトランプカード一式をランダムに \(4\) 枚ずつまとめて \(13\) 個の山を作ったとする。山の例を次に示す:

\[ {\small \begin{alignedat}{3} & \left\{ 2\spadesuit,\ 2\heartsuit,\ 9\diamondsuit,\ K\diamondsuit\right\} ,\hspace{4pt} && \left\{ A\spadesuit,\ A\heartsuit,\ 3\spadesuit ,\ 3\diamondsuit\right\} , \hspace{4pt} && \left\{ A\diamondsuit ,\ 4\clubsuit,\ 5\clubsuit,\ Q\clubsuit\right\} ,\\ & \left\{ 2\diamondsuit,\ 4\heartsuit,\ 5\heartsuit,\ 5\spadesuit\right\} , \hspace{4pt} && \left\{ A\clubsuit,\ 7\clubsuit,\ 7\spadesuit ,\ 7\heartsuit\right\} , \hspace{4pt} && \left\{ 4\spadesuit ,\ 6\spadesuit,\ 6\diamondsuit,\ 6\clubsuit\right\} ,\\ & \left\{ 3\heartsuit,\ 3\clubsuit,\ 8\spadesuit,\ 8\heartsuit\right\} , \hspace{4pt} && \left\{ 2\clubsuit,\ K\clubsuit,\ K\heartsuit ,\ 10\heartsuit\right\} , \hspace{4pt} && \left\{ 4\diamondsuit ,\ 5\diamondsuit,\ 9\spadesuit,\ 9\heartsuit\right\} ,\\ & \left\{ Q\spadesuit,\ Q\heartsuit,\ Q\diamondsuit,\ Q\clubsuit\right\} , \hspace{4pt} && \left\{ 6\heartsuit,\ J\spadesuit,\ J\diamondsuit ,\ J\clubsuit\right\} , \hspace{4pt} && \left\{ 7\diamondsuit ,\ 8\diamondsuit,\ 8\clubsuit,\ 9\clubsuit\right\} ,\\ & \left\{ 10\spadesuit,\ J\heartsuit,\ 10\diamondsuit,\ 10\clubsuit\right\} \end{alignedat}} \]

[山は自由に作って構わない。これは例の一つに過ぎない。] このとき、\(13\) 個の山から \(1\) 枚ずつカードを取ることで、それぞれの数字のカードを \(1\) 枚ずつ (\(1\) を \(1\) 枚、\(2\) を \(1\) 枚、…) 揃えることが必ずできる。

実際、任意に選んだ \(p\) 個の山には少なくとも \(p\) 個の異なる数字が含まれるので、\(A_{i} = \{i \text{ 番目の山に含まれる数字}\}\) と定めれば定理 8.5.1 の仮定が満たされる。

[定理 8.5.1 の証明] まず、\(n\) 個の集合 \(A_{1},A_{2},\ldots,A_{n}\) は全て有限集合だと一般性を失うことなく仮定する (もしそうでないなら、無限集合をそれぞれ任意の \(n\) 要素部分集合に置き換える。このとき仮定 \(\left\vert A_{i_{1}}\cup A_{i_{2}}\cup\cdots\cup A_{i_{p}}\right\vert \geq p\) は保たれる ── その理由を理解しておくこと！)。

さらに、\(n\) 個の集合 \(A_{1},A_{2},\ldots,A_{n}\) はどれも整数を含まないと一般性を失うことなく仮定する (そうでないなら、集合の要素を整数でないものに置き換える)。

\(X=\left\{ 1,2,\ldots,n\right\} \), \(\ Y=A_{1}\cup A_{2}\cup \cdots\cup A_{n}\) と定める。\(X\) と \(Y\) は有限集合であり、共通要素を持たない。

単純グラフ \(G\) を次のように定義する:

\(G\) の頂点は \(X\cup Y\) の要素である。
頂点 \(x \in X\) と頂点 \(y \in Y\) は \(y \in A_{x}\) のとき、かつそのときに限って隣接する。これ以外に隣接する二頂点は存在しない。

このとき \(\left( G,X,Y\right) \) は二部グラフである。さらに、定理の仮定「任意の \(p\in\left\{ 0,1,\ldots,n\right\}\) に対して \(\left\vert A_{i_{1}}\cup A_{i_{2}}\cup\cdots\cup A_{i_{p}}\right\vert \geq p\) が成り立つ」より、この二部グラフは Hall 条件を満たす。よって Hall の結婚定理 (定理 8.3.4) より、グラフ \(G\) は \(X\)-完全マッチングを持つ。このマッチングは次の形をしている:

\[ \left\{ \left\{ 1,a_{1}\right\} ,\ \left\{ 2,a_{2}\right\} ,\ \ldots ,\ \left\{ n,a_{n}\right\} \right\} \]

ここで \(a_{1},a_{2},\ldots,a_{n}\in Y\) である (先述したように \(\left( G,X,Y\right) \) は二部グラフなので、頂点 \(1,2,\ldots,n\in X\) のパートナーは \(Y\) に属する)。マッチングに属する任意の二辺は共通の端点を持たないので、\(a_{1},a_{2},\ldots,a_{n}\in Y\) は相異なる。さらに、\(i\in\left\{ 1,2,\ldots,n\right\} \) は \(a_{i} \in A_{i}\) を満たす (\(G\) で頂点 \(i\) と頂点 \(a_{i}\) が隣接するため)。よって \(a_{1},a_{2},\ldots,a_{n}\) は探していた \(n\) 個の相異なる要素である。以上で定理 8.5.1 は証明された。□

逆に、定理 8.5.1 を使った Hall の結婚定理 (定理 8.3.4) の導出も難しくない。つまり、定理 8.5.1 は Hall の結婚定理と同値な命題である。実は、Hall が最初に発見した命題 [Hall35, Theorem 1] は定理 8.5.1 だった。

Hall の結婚定理の二つ目の表現を次に示す。こちらも集合理論的な表現である:

定理 8.5.4

[SCR の存在] \(A_{1},A_{2},\ldots,A_{n}\) を \(n\) 個の集合、\(B_{1},B_{2},\ldots,B_{m}\) を \(m\) 個の集合とする。任意の \(p\in\left\{ 0,1,\ldots,n\right\}\) と任意の自然数 \(i_{1}, i_{2}, \ldots, i_{p}\) が \(1\leq i_{1} < i_{2} < \cdots < i_{p}\leq n\) を満たすとき、少なくとも \(p\) 個の \(j\in\left\{ 1,2,\ldots,m\right\} \) において和集合 \(A_{i_{1}}\cup A_{i_{2}}\cup\cdots\cup A_{i_{p}}\) と \(B_{j}\) が共通の要素を持つと仮定する。このとき単射 \(\sigma\colon \left\{ 1,2,\ldots,n\right\} \rightarrow\left\{ 1,2,\ldots,m\right\} \) であって全ての \(i\in\left\{ 1,2,\ldots,n\right\} \) が \(A_{i}\cap B_{\sigma\left( i\right) }\neq\varnothing\) を満たすものが存在する。

[証明] 読者に任せる。ここでも、適切な二部グラフを構築して Hall の結婚定理を適用すればよい。□

[定理の名前にある「SCR」は 共通代表系 (system of common representatives) を意味する。]

代表系に関する本書よりずっと詳細な解説については [MirPer66] を参照してほしい。