Hallの結婚定理

$A=\{a_1,\dots,a_n\}$ とし、$U_i:=N(\{a_i\})\subset B$ とおく。$I\subset\{1,\dots,n\}$ と $S=\{a_i\mid i\in I\}$ について $U(I)=N(S)$ である。$A$ を飽和するマッチング $M$ があれば、$a_i$ と $M$ で結ばれる頂点を $f(i)$ とすると $f$ は相異なる代表系である。逆に相異なる代表系 $f$ があれば、辺 $a_if(i)$（$i=1,\dots,n$）の集合は、$a_i$ が相異なり $f(i)$ も相異なるのでマッチングで、$A$ を飽和する。したがって主張は thm-hall-marriage-theorem と同値である。$\square$

$T$ のある頂点 $y$ が $M$ で飽和されない場合に 1 が、$T$ のすべての頂点が $M$ で飽和される場合に 2 が成り立つことを示す。
（1 の場合）$y$ で終わる $x_0$ から出る $M$ 交互道 $x_0,y_1,x_1,\dots,x_{k-1},y_k$（$y_k=y$）をとる。この道の $M$ に属する辺 $y_jx_j$（$1\le j\le k-1$）を $M$ から除き、$M$ に属さない辺 $x_{j-1}y_j$（$1\le j\le k$）を加えた集合を $M'$ とする。$M'$ の辺の個数は $|M|-(k-1)+k=|M|+1$ である。$M'$ がマッチングであることを確かめる。道の上にない頂点に接続する $M'$ の辺は $M$ の辺と同じで、高々 1 本である。$x_0$ は $M$ で飽和されないので、$M'$ の辺で $x_0$ に接続するのは $x_0y_1$ だけである。$x_j$（$1\le j\le k-1$）に接続する $M$ の辺は $y_jx_j$ だけであり（$M$ はマッチング）、これが除かれて $x_jy_{j+1}$ が加わるので、$M'$ の辺でも 1 本である。$y_j$（$1\le j\le k-1$）でも同様に $y_jx_j$ が除かれて $x_{j-1}y_j$ が加わる。$y_k$ は $M$ で飽和されないので、$M'$ の辺で接続するのは $x_{k-1}y_k$ だけである。したがって $M'$ はマッチングであり、$M$ で飽和される頂点はすべて $M'$ でも飽和され、さらに $x_0$ が飽和される。
（2 の場合）$T$ のすべての頂点が $M$ で飽和されるとする。$y\in T$ に $M$ で結ばれる頂点を $m(y)\in A$ と書く。
まず、$m$ が $T$ から $S\setminus\{x_0\}$ への全単射であることを示す。$y\in T$ で終わる交互道 $P=x_0,y_1,x_1,\dots,y_k$（$y_k=y$）をとり、$x:=m(y)$ とおく。$x_0$ は飽和されないので $x\ne x_0$ である。$x$ が $P$ の上にあるとすると $x=x_j$（$1\le j\le k-1$）であり、$P$ の辺 $y_jx_j$ が $M$ に属するので、$x_j$ の $M$ での相手は $y_j$ である。一方 $x_j$ の相手は $y_k$ でもあるから $y_j=y_k$ となり、$P$ の頂点が相異なることに反する。よって $x$ は $P$ の上になく、$P$ に辺 $yx\in M$ を付け加えた列は $x_0$ から出る $M$ 交互道で、$x\in S\setminus\{x_0\}$ である。$M$ がマッチングなので $m$ は単射である。逆に $x\in S\setminus\{x_0\}$ で終わる交互道の最後の辺は $M$ に属する辺 $y_kx$ であり、その手前までの列は $y_k$ で終わる交互道だから、$y_k\in T$ かつ $m(y_k)=x$ である。よって $m$ は全射でもあり、$|T|=|S|-1$ である（$S\subset A$ は有限集合）。
次に $N(S)=T$ を示す。$T$ の頂点 $y_k$ は交互道の直前の頂点 $x_{k-1}\in S$ と隣接するので $T\subset N(S)$ である。逆に $x\in S$ と、$x$ に隣接する $y\in B$ をとる。辺 $xy$ が $M$ に属するなら、$x\ne x_0$ であり、上の全射性から $x=m(y')$ となる $y'\in T$ があって、$M$ での相手は一意なので $y=y'\in T$ である。辺 $xy$ が $M$ に属さないなら、$x$ で終わる交互道 $P$（$x=x_0$ なら列 $x_0$ だけ）をとる。$y$ が $P$ の上にあれば、$P$ を $y$ で打ち切った列が $y$ で終わる交互道なので $y\in T$ である。$y$ が $P$ の上になければ、$P$ の最後の辺は $M$ に属する（または $P$ は $x_0$ だけ）ので、$P$ に辺 $xy\notin M$ を付け加えた列は交互道であり、$y\in T$ である。よって $N(S)\subset T$ であり、$|N(S)|=|T|=|S|-1$ である。$\square$

（必要性）相異なる代表系 $f$ があるとする。$I\subset\{1,\dots,n\}$ について $f(I)\subset U(I)$ であり、$f$ は単射なので $|U(I)|\ge|f(I)|=|I|$ である。
（十分性）Hall の条件を仮定する。$A:=\{1,\dots,n\}$、$B:=Y$ とし、$i\in A$ と $y\in U_i$ を辺で結ぶ二部グラフ $G$ を考える（$A$ と $Y$ は交わらない別々の集合とみなす）。$S\subset A$ について $N(S)=U(S)$ である。$M$ を $G$ のマッチングとし、$A$ に $M$ で飽和されない頂点 $x_0$ があるとする。lem-hall-marriage-theorem-augment の 2 が成り立つなら、$S\subset A$ で $|U(S)|=|N(S)|=|S|-1<|S|$ となり、Hall の条件に反する。したがって同じ補題の 1 が成り立ち、飽和される $A$ の頂点が 1 つ多いマッチングが得られる。空のマッチングから始めてこれを繰り返すと、$n$ 回以内に $A$ を飽和するマッチング $M$ が得られる。$i\in A$ と $M$ で結ばれる頂点を $f(i)$ とすると、$f(i)\in U_i$ であり、$M$ の辺は端点を共有しないので $f$ は単射である。すなわち $f$ は相異なる代表系である。$\square$

任意のマッチング $M$ と $S\subset A$ をとる。$S$ の頂点で $M$ に飽和されるものは、$M$ で相異なる $N(S)$ の頂点と結ばれるので $|N(S)|$ 個以下であり、$S$ の頂点のうち少なくとも $|S|-|N(S)|$ 個は飽和されない。$M$ の各辺はちょうど 1 つの $A$ の頂点を飽和するので $|M|\le|A|-(|S|-|N(S)|)$ であり、$S$ を動かして $|M|\le|A|-\delta$ を得る。
逆に、$B$ に新しい頂点 $\delta$ 個からなる集合 $D$ を付け加え、$D$ の各頂点を $A$ のすべての頂点と辺で結んだ二部グラフ $G'$（二部分割 $(A,B\cup D)$）を考える。空でない $S\subset A$ について $G'$ での近傍は $N(S)\cup D$ なので、その大きさは $|N(S)|+\delta\ge|S|$ である。$S=\emptyset$ では不等式は自明である。cor-hall-marriage-theorem-bipartite により、$G'$ に $A$ を飽和するマッチング $M'$ がある。$M'$ の辺のうち $D$ の頂点を端点とするものは高々 $\delta$ 本なので、それらを除くと $G$ のマッチングで大きさが $|A|-\delta$ 以上のものが得られる。$\square$

第 $j$ 列にまだ現れていない数の集合を $U_j\subset\{1,\dots,n\}$ とする（$j=1,\dots,n$）。第 $j$ 列には相異なる $r$ 個の数があるので $|U_j|=n-r$ である。また、各数 $s$ は各行にちょうど 1 回、合わせて $r$ 回現れ、同じ列に 2 回は現れないので、ちょうど $r$ 個の列に現れ、ちょうど $n-r$ 個の列の $U_j$ に属する。
列の集合 $I$ をとり、$j\in I$ と $s\in U_j$ の組 $(j,s)$ の個数を 2 通りに数える。$j$ ごとに数えると $|I|(n-r)$ 個である。$s$ ごとに数えると、組に現れる $s$ は $U(I)$ の元で、各 $s$ は高々 $n-r$ 個の $j$ と組になるので、個数は $|U(I)|(n-r)$ 以下である。$n-r>0$ なので $|U(I)|\ge|I|$ となり、$(U_j)_{j=1}^n$ は Hall の条件を満たす。thm-hall-marriage-theorem により相異なる代表系 $f$ がある。$(f(1),\dots,f(n))$ は $\{1,\dots,n\}$ の相異なる $n$ 個の元の並びなので $1,\dots,n$ がちょうど 1 回ずつ現れ、$f(j)\in U_j$ なので第 $j$ 列の既存の数と重ならない。この並びを第 $r+1$ 行として付け加えればよい。後半は $r$ についての繰り返しで従う。$\square$

$P=(p_{ij})$ の正の成分の個数 $c(P)$ についての帰納法で示す。各行の和が $1$ なので各行に正の成分があり、$c(P)\ge n$ である。
まず、置換 $\sigma$ で $p_{i\sigma(i)}>0$（$i=1,\dots,n$）となるものがあることを示す。$U_i:=\{j\mid p_{ij}>0\}$ とおく。行の集合 $I$ について、$i\in I$ の行の正の成分はすべて $U(I)$ の列にあるので、
$$|I|=\sum_{i\in I}\sum_{j=1}^np_{ij}=\sum_{i\in I}\sum_{j\in U(I)}p_{ij}\le\sum_{j\in U(I)}\sum_{i=1}^np_{ij}=|U(I)|$$
である（成分は $0$ 以上で、各列の和は $1$）。thm-hall-marriage-theorem により相異なる代表系 $\sigma$ があり、$\sigma$ は $\{1,\dots,n\}$ から自分自身への単射だから置換で、$p_{i\sigma(i)}>0$ である。
$\lambda:=\min_ip_{i\sigma(i)}>0$ とおく。$\lambda=1$ なら、各行の和が $1$ なので $P$ の各行は $(i,\sigma(i))$ 成分だけが $1$ で、$P=Q_\sigma$ である。$c(P)=n$ のときは、各行の正の成分がちょうど 1 つで、それは $(i,\sigma(i))$ 成分であり、行の和から $1$ に等しいので、やはり $P=Q_\sigma$ である。$\lambda<1$ のとき、$P':=(P-\lambda Q_\sigma)/(1-\lambda)$ とおく。$P'$ の成分は $0$ 以上で、各行・各列の和は $(1-\lambda)/(1-\lambda)=1$ なので $P'$ は二重確率行列である。$P'$ の正の成分は $P$ の正の成分の位置にしかなく、最小値 $\lambda$ をとる位置では $0$ になるので $c(P')< c(P)$ である。帰納法の仮定により $P'$ は置換行列の凸結合であり、$P=\lambda Q_\sigma+(1-\lambda)P'$ も置換行列の凸結合である。$\square$