定理5(Hallの結婚定理) $A_i \subseteq S (0\leq i \leq n - 1)$ をとる。 $m_i = |A_i|$ とし、 $m_0 \leq m_1\leq \cdots \leq m_{n - 1}$ を仮定し、 $A_0,A_1,A_2,\ldots ,A_{n - 1}$ がHall条件を満たすならば $N(A_0,A_1,\ldots,A_{n - 1}) \geq F_n(m_0,m_1,\ldots,m_{n - 1})$

(証明) $n$ に関する帰納法で示す。 $n = 1$ のときは自明。

$n \geq 2$ のとき、次の二つの場合に分けて考える。

(1)臨界ブロックがない場合

$a \in A_0$ を任意に1つ選んで、各 $A_i (1 \leq i \leq n - 1)$ から $a$ を除いて得られる集合を $A_i (a)$ とおく。 $A_0,A_1,\ldots,A_{n - 1}$ はHall条件を満たしかつ臨界ブロックが存在しないため、どの $k$ 個を選んでもその $k$ 個の集合の和集合の要素数は $k + 1$ 以上。ゆえに $A_0,A_1 (a),A_2 (a),\ldots,A_{n - 1} (a)$ もHall条件を満たす。

したがって帰納法の仮定と補題から

$\begin{align} N(A_0,A_1,\ldots,A_{n - 1}) &\geq \sum_{a \in A_0} f_{n - 1} (|A_1(a)|,|A_2(a)|,\ldots,|A_{n - 1}(a)|) \\ &\geq \sum_{a \in A_0} f_{n - 1}(m_1 - 1,\ldots,m_{n - 1} - 1) \\ &= m_0 f_{n - 1}(m_1 - 1,\ldots,m_{n - 1} - 1) \\ &= m_0\sum_{i = 0}^{n - 2}(m_{i + 1} - 1 - i)_{*} \\ &= (m_0 - 0) \sum_{i = 1}^{n - 1}(m_{i} - i)_{*} \\ &= F_n(m_0,m_1,\ldots,m_{n - 1}) \end{align}$
となってこの場合では示された。

(2)臨界ブロック $\{A_{v_0},A_{v_1},\ldots,A_{v_{k - 1}}\} (v_0 < v_1 < \ldots < v_{k - 1} ,0 < k < n)$ が存在する場合
$A_{v_0}, A_{v_1} ,\cdots, A_{v_{k -1}}$ 以外の集合を $A_{\mu_0},A_{\mu_1},\cdots,A_{\mu_{l - 1}}$ とおく。 $k + l = n$ である。
各 $0 \leq i \leq l - 1$ に対して $A_{\mu_i}$ から $B = \cup_{i = 0}^{k - 1} A_{v_i}$ の要素をすべて除いて得られる集合を $A\prime _{\mu_i}$ とする。
$\{A_{v_0},A_{v_1},\ldots,A_{v_{k - 1}}\}$ と $\{A\prime _{\mu_0}, A\prime_{\mu_1},\ldots,A\prime_{\mu_{l - 1}}\}$ はHall条件を満たしている。
また、 $\{A_{v_0},A_{v_1},\ldots,A_{v_{k - 1}}\}$ と $\{A\prime _{\mu_0}, A\prime_{\mu_1},\ldots,A\prime_{\mu_{l - 1}}\}$ の個別代表系は互いに排反である。

したがって
$\begin{align} N(A_0,A_1,\ldots,A_{n - 1}) &= N(A_{v_0},A_{v_1},\ldots,A_{v_{k - 1}})N(A\prime _{\mu_0},A\prime _{\mu_1},\ldots,A\prime _{\mu_{l - 1}}) \\ &\geq f_k(m_{v_0},m_{v_1},\ldots,m_{v_{k -1}}) f_l (|A\prime _{\mu_0}|,|A\prime _{\mu_1}|,\ldots,|A\prime _{\mu_{l - 1}}|) \\ &\geq f_k(m_{v_0},m_{v_1},\ldots,m_{v_{k - 1}}) f_l(m_{\mu_0} - k,m_{\mu_1} - k ,\ldots,m_{\mu_{l - 1}}) \\ &\geq f_k(m_0,m_1,\ldots,m_{k - 1})f_l(m_{\mu_0} - k,m_{\mu_1} - k,\ldots,m_{\mu_{l - 1}} - k) \\ \end{align}$

ここで $m_{v_{k - 1}} \leq |B| = k$ であり、 $k \leq r \leq v_{k - 1}$ のとき $m_r \leq m_{v_{k - 1}}$ であるから
$m_r - r \leq m_{v_{k - 1}} - r \leq 0$ となって、 $(m_r - r)_{*} = 1$ となる。

また、 $\mu_i \leq v_{k - 1}$ のとき $m_{\mu_i} \leq m_{v_{k - 1}}$ なので $m_{\mu_i} - k \leq m_{v_{k - 1}} - k \leq 0$
したがって $(m_{\mu_i} - k - i)_{*} = 1$ となる。

ゆえに
$\begin{align} f_k(m_0,m_1,\ldots,m_{k - 1}) &= \prod_{0 \leq i \leq k - 1} (m_i - i)_{*} \\ &= \prod_{0 \leq i \leq v_{k - 1}}(m_i - i)_{*} \end{align}$
同様にして
$\begin{align} f_l(m_{\mu_0} - k,m_{\mu_1} - k, \ldots,m_{\mu_{l - 1} - k}) = \prod_{v_{k - 1} < j < n} (m_j - j)_{*} \end{align}$

したがって $f_k(m_0,m_1,\ldots,m_{k - 1})f_l(m_{\mu_0} - k ,m_{\mu_1} - k ,\ldots, m_{\mu_{l - 1}} - k) = F_n(m_0,m_1,\ldots,m_{n - 1})$ であって、この場合でも示された。

2022-12-03

Hallの結婚定理(1)

　この記事では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