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

ようやく本題に入ります。次のステートメントの内容を証明します。

定理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})$ であって、この場合でも示された。