Hallの結婚定理(1) - uw_yu1rabbit’s blog

　この記事ではHallの結婚定理の証明のうち、個別代表系(SDR)というものを用いた証明を扱います。

まず、Hallの結婚定理のステートメントを確認します。

Hallの結婚定理 $X,Y$ を部集合とする二部グラフGにおいて、 $X$ から $Y$ への完全マッチングが存在するための必要十分条件は、任意の $A \subseteq X$ に対して

$|\Gamma(A)| \geq |A|$ が成り立つことである。

頂点 $a$ について $\Gamma(a)$ は $a$ に隣接する頂点の個数を指し、集合 $X$ について $|X|$ は $\sum_{a \in A} \Gamma(a)$ を意味します。

今回はこちらのステートメントではなく、これと同値になる定理を示すことにします。

定理を紹介する前に導入すべき定義と、いくつか示しておくべきことがあるので、それを証明します。

定義1(Hall条件)　 $S$ を有限集合、 $A_0,A_1,A_2,\ldots,A_{n - 1}$ をSの部分集合とする。任意の自然数 $k\leq n$ についてある $k$ 個の $A_{i_0},A_{i_1},\ldots,A_{i_{k - 1}}$ の和集合の要素数が少なくとも $k$ 個であるとき、 $A_0,A_1,A_2,\ldots,A_{n - 1}$ はHall条件を満たすという。

定義2(臨界ブロック) 定義1と同じ条件のもと、ある $k$ 個の集合 $A_{i_0},A_{i_1},\ldots,A_{i_{k - 1}}$ であるとき、 $\{A_{i_0},A_{i_1},\ldots,A_{i_{k - 1}}\}$ を臨界ブロックという。

定義3(個別代表系)　集合 $A_i (0\leq i\leq n - 1)$ から要素 $a_i$ を一つずつ選ぶ。これらがすべて相異なるとき、 $a_0,a_1,\ldots,a_{n - 1}$ を $A_0,A_1,\ldots,A_{n - 1}$ の個別代表系(System of Distinct Representive, SDR)という。

以下、非減少整数列 $m_0,m_1,\ldots,m_{n - 1}$ に対して関数

$F_n(m_0,m_1,\ldots,m_{n - 1}) = \prod_{i = 0}^{n - 1} (m_i - i)_{*}$

を定義します。ただし $(a)_{*} = max\{1,a\}$ とします。

また、 $\{m_i = |A_i|\}$ を非減少であるとします。

補題4　整数 $n \geq 1$ に対して写像 $f_n : \mathbb{Z}^n \rightarrow \mathbb{N}$ を

$f_n(a_0,a_1,\ldots,a_{n -1}) = F_n(m_0,m_1,\ldots,m_{n -1})$

で定める。ただし、 $m_0,m_1,\ldots,m_{n -1}$ は $a_0,a_1,\ldots a_{n -1}$ の順序交換で定められる非減少列とする。このとき $f_n$ は各 $a_i$ の非減少関数となる。

(証明)

$f_n(a_0,a_1,\ldots,a_i,\ldots,a_{n - 1}) \leq f_n(a_0,a_1,\ldots,a_i + 1,\ldots,a_{n + 1})$ であることを示せばよい。

$k$ を( $m_k = a_i$ かつ $k = n - 1$ )または( $m_k \lt m_{k + 1}$ )を満たすindexとする。このとき、 $(a_0,a_1,\ldots,a_i + 1,\ldots,a_{n - 1})$ は $(m_0,m_1,\ldots,mi +1,\ldots,m_{n - 1})$ で与えられる。

ゆえに定義から $F_n(m_1,\ldots,m_k,\ldots,m_{n - 1})\leq F_n(m_1,\ldots,m_k + 1,\ldots,m_{n - 1})$ である。

ここで、 $A_0,A_1,\ldots,A_{n - 1}$ の個別代表系の総数を $N(A_0,a_1,\ldots,A_{n -1})$ とおく。

続きです。
uw-yu1rabbit.hatenablog.com