Hall <=> Koenig <=> Dilworth

hall.txt

http://robertborgersen.info/Presentations/GS-05R-1.pdf

- Koenig: 二部グラフ G について、最大マッチングと最小点カバーの大きさは等しい。
- Koenig-Egerváry: 01 行列 B に対し、それを二部グラフとしてみなしたときの最大マッチングの大きさを term rank と、点カバーをカバーと呼ぶ。
  term rank は最小のカバーの大きさに等しい。
- Birkhoff-Von Neumann: 二重確率行列: 全ての要素が非負な正方行列であって、行の和と列の和がすべて 1 であるもの
  permutation matrix: 二重確率行列であって要素が 0 または 1 であるもの
  二重確率行列は permutation matrix の convex combination で表せる。
- Hall: X を集合、S_1, ..., S_n を X の部分集合とする。任意の [n] の部分集合 A に対して |\bigcup_{i \in A} S_i| >= |A| が成立するのであれば、
  相異なる x_i in S_i がとれる。
- Dilworth: P: poset, r := P の antichain の最大長 ==> P は r 個の互いに素な chain に分解できる。

## Koenig <=> Koenig-Egerváry
言い換えただけなので明らか。

## Hall => Koenig-Egerváry
p := (term rank), q := min #(カバー) とする。 
p >= q を示す。最小のカバーにおいて行が r 個、列が s 個選ばれているとする。 
行列の行と列を permute して、行 1 <= i <= r および列 1 <= j <= s が選ばれているとしてよい。 
1 <= i <= r に対し A_i := {j | j > s, B_{ij} = 1} とおく。 任意の `S \subset [r]` に対して |\bigcup_{S} A_i| >= |S| が成立する。
なぜなら、そうでなければ |\bigcup_{S} A_i| < |S| なる S がとれるが、S に含まれる行の代わりに \bigcup_{S} A_i に含まれる列を選ぶことでより小さいカバーが作れるため。 
以上より、Hall の定理の前提条件が言えたので、 j > s の範囲に r 個の行それぞれに対応する 1 がとれる。
同様に、i > r の範囲に s 個の列それぞれに対応する 1 が取れる。
これらは別の行にあるため、合わせると大きさ r + s のマッチングをなす。

## Koenig-Egerváry => Hall
X を集合、S_1, ..., S_n を X の部分集合とする。任意の [n] の部分集合 A に対して |\bigcup_{i \in A} S_i| >= |A| を仮定する。
このとき、n * m 行列 B を B_{ij} := (j in S_i ? 1 : 0) で定める。このとき B の最小カバーの大きさは n である。
なぜなら、最小カバーにおける選ばれた行と列の個数をそれぞれ r, s とおくと、選ばれなかった n - r 個の行について、
Hall の定理の仮定からそこに含まれる 1 は n - r 列以上に含まれる。よって s >= n - r でなければならず、r + s >= n が結論できる。
Koenig-Egerváry から、大きさ n のマッチングが存在し、そのようなマッチングは相異なる x_i in S_i を定める。
マッチングを i <==> M_i としたとき、x_i := M_i とすればよい。

## Dilworth => Hall
X を集合、S_1, ..., S_n を X の部分集合とする。任意の [n] の部分集合 A に対して |\bigcup_{i \in A} S_i| >= |A| を仮定する。
P := {S_1, ..., S_n, x_1, ..., x_m} を x_i < S_j iff x_i in S_j という順序が入った poset とする。
このとき {x_1, ..., x_m} は P において最大の antichain である。よって大きさ m の分解が存在し、chain の最大長が 2 であることから、
長さ 2 の chain が n 個、長さ 1 の chain が m-n 個、という分解であるはず。長さ 2 の chain が所望の選択関数を与える。

## Koenig => Dilworth
P: poset に対し以下のように二部グラフを作る。
n := |P| とする。左右それぞれに n 頂点 L1,...,Ln, R1,...,Rn を配置し、Lu -> Rv <=> u < v in P という条件で辺を張る。
Koenig の定理から、最大マッチングの大きさと最小点カバー C の大きさは等しい。それらの大きさを k とおく。
P は n-k 個の chain に分割できる。
一方で、P の点であって C に対応する点が含まれないもの全体の集合を L とおくと、|L| >= n-k である。
L は antichain である。なぜなら仮に a < b in L としたとき、C は La -> Rb という辺をカバーできていないことになるため。
よって |L| <= n-k より実は |L| = n-k であり、Dilworth の定理が成立する。