Chapter5 Systems of Distinct Representatives 照山順一

system of distinct representative(以下SDR) 集合列S1,S2,…,Smに対するSDRとは、 以下の条件を満たす異なる要素の列 x1,x2,…,xmのこと。 条件： この様な列が存在するのか？->結婚問題 女性は知っている男性とのみ結婚できる。 すべての女性が結婚できる方法は？ 3 5 6 2 3 4 1 4 3 4 5 6 1 2

Hall’s Condition 3 5 6 2 3 4 1 4 3 4 5 6 1 2 {1,2,3,4,5,6}

定理5.1結婚定理(Hall’s marriage theorem) ｢集合S1,…,SmがSDRを持つこと｣は、 ｢Hall’s Conditionを満たすこと｣の必要十分条 件である。 証明の方針：(十分性は明らかなので、必要性のみ) mに関する帰納法。 m=1の時は明らか。 m個より少ない集合について成り立つと仮定。 2つの場合に分けて考える。

Case1 すべてのkについて、任意のk個の集合の 和集合はkより多く要素をもつ。 Hall’s condition を満たす。 (どのk集合を持ってきても和集合の大きさはk以上) xを使用しないSDRが存在する。 xを加えて全体のSDRとする。

Case2 あるkについて、k個の集合の和集合が ちょうどk個の要素をもつ。 k集合のSDR要素を取り除く 和集合の大きさがsより小さいとすると、 もともとこの集合とk集合の和集合の 大きさがk+sより小さくなってしまい、 仮定に矛盾。 Hall’s condition が満たされている。 なぜか？

Hall’s Condition 一般にはHall’s conditionが満たされて いるかを確認するのは大変。 しかし、集合の性質がわかっていると 楽になることもある。

[系5.2] 集合S1,…,Smをn要素集合のr要素部分集合と し、それぞれの要素はd個の集合に属してい る。もし、　　　ならば、集合S1,…,Smは SDRを持つ。 [証明] 要素数をダブルカウンティング。 集合S1,…,SmがSDRを持たないとして矛盾を導く。 あるk個の集合(Si1,…, Sik)に対して和集合( Y )の要素 数がkより小さい。(Hall’s conditionから) dxをこの集合に含まれているxの数とすると、

要素に色(赤or青)が付いた問題を考える。 集合と色分けされた要素が与えられて、 できるだけ赤の要素が少ないSDRを作りたい。 [定理5.3] ｢集合S1,…,Smが赤の要素が高々tのSDRを持つ｣こと は、 ｢集合S1,…,SmがSDRを持ち、すべてのkに対して任 意のk個の集合の和集合が少なくともk-tの青の要素 をもつ｣ ことの必要十分条件である。 十分性は明らか。

十分性 3 5 6 2 3 4 3 4 5 6 1 2 5 3 ・・・ 4 2 どのようにk個の集合を選んでも、少なくともk-t個の青要素がある

定理5.3の証明 仮定：｢集合S1,…,SmがSDRを持ち、すべてのkに対して任意のk個の集合の和集合が少なくともk-tの青の要素をもつ｣ 仮定：|R|>tとする。(そうでないとすると簡単) 集合S1,…,Smを集合S1,…,Sm ,Sm+1,…,Sm+rに拡張 する。(Sm+1=…=Sm+r =R , r = |R| - t ) ｢集合S1,…,Smが赤の要素が高々tのSDRを持つ｣ ｢集合S1,…,Sm ,Sm+1,…,Sm+rがSDRを持つ｣

定理5.3の証明 示すこと：これらの集合がHall’s conditionを満たす。 3 5 6 2 3 4 3 4 5 6 2 4 7 … 1 2 これらの集合のみでの集合らは、 仮定でSDRをもともと持っているのでOK。 こちらの集合も含んでいる場合 和集合の青の要素数の仮定から 右側から選んだ集合の数

(復習)SDRとHall’s condtion

5.2Two applications Hall’s Theoremを使って集合系に関係のなさ そうにみえる定理を証明。 5.2.1 Latin rectangles(ラテン長方形) 1からnが各列に1つずつ、各行には高々1つ の行列。 2 5 4 1 3 3×5のラテン長方形

r×nラテン長方形は、(r+1)×nラテン長方形 に拡張することができる。 [証明] 第j行にない数字の集合をSjとする。 この時、Sjはすべて n - r 個の要素を持ち、 それぞれの数字は n - r 個の集合に属している。 系5.2よりこの集合系はSDRを持つ。 2 5 4 1 3 3 4 5 2 1 [系5.2] 集合S1,…,Smをn要素集合のr要素部分集合とし、 それぞれの要素はd個の集合に属している。 もし、　　　ならば、集合S1,…,SmはSDRを持つ。 3×5のラテン長方形から 4×5のラテン長方形へ

Decomposition of doubly stochastic matrices (二重確率行列の分解) 5.2.2 Decomposition of doubly stochastic matrices (二重確率行列の分解) [用語の準備] doubly stochastic matrix(二重確率行列)： 非負実数を要素に持つ行列で、 各行、各列の要素の和が１。 permutation matrix(置換行列)： 各行、各列に１が１つ convex combination of matrices(凸結合)：

[Birkhoff-Von Neumann Theorem] すべての二重確率行列は、 置換行列の凸結合である。 [証明]より一般的なことを証明する。 Aの非負要素の数に関して帰納法。 もし、ちょうどnならば簡単。 nより多いとし、その数より少ないところでは 定理が成り立つと仮定する。

この時、S1,…,SmがHall’s condtionを満たす。 Siを第i行に関して0でない要素がある 列番号の集合とする。 この時、S1,…,SmがHall’s condtionを満たす。 もし満たさないとすると、k行取ってきたときにそ の中で0でない要素をもつ列がk未満である。この とき列から見た要素の和は高々(k-1)g 、行から見た 和はkg であり矛盾。 あるSDRが存在し、これをもとに分解でき ることを証明する。 次のスライドで少し具体的に。

5.3 Min-max theorems [定理5.5] Aをm×n行列とする。 独立な1の数の最大値は、 Aの1をすべてカバーするのに必要な行と列 の数の最小値と等しい。

定理5.5の証明 r：独立な1の数の最大値 R ：Aの1をすべてカバーするのに必要な 行と列の数の最小値 明らかに、Rはr以上。

定理5.5の証明 Siをi行で1がある列の番号の集合とする。 S1,…,SaがSDRを持つことを示す。 この部分で a個の独立な1が とれることを示す。 Siをi行で1がある列の番号の集合とする。 S1,…,SaがSDRを持つことを示す。 持たないとすると、Hall’s theoremからあるk行を 持ってきたときにその部分の1の数がkより小さく なる。つまりこのk行分をkより少ない列でカバー できる。しかし、カバーに必要な行と列の数がa+b より小さくなり矛盾となる。 左下の部分についても同様にすると、

5.4 Matching in bipartite graphs 2部グラフGはAからBへのマッチングをもつのか？ Aの各頂点に関して隣接頂点の集合をとり、 その集合系がSDRを持つか？

[定理5.6](Hall’s Theoremの言い換え) ｢二部グラフGがAからBへのマッチングをも つ｣ことは、 ｢Aのすべてのk頂点部分集合は少なくともk 個の隣接頂点をもつ｣ことの必要十分条件で ある。 [命題5.7] X ：n要素集合。 任意の に対してXのすべてのk 要素部分集合をどの二つも一致することな く(k+1)要素部分集合に拡張できる。 定理5.6を用いて 以下の命題を証明する。

n=5,k=2 3 5 2 2 4 5 3 1 4 1

命題5.7の証明 Aの頂点：Xのk要素部分集合 Bの頂点：Xの(k+1)要素部分集合 包含関係の成り立つ頂点間に枝が張られている。 示すこと：AからBへの完全マッチングが存在している。 Hall’s Condition

残りの部分は、最大マッチングと最小 頂点被覆の話なので、グラフ理論の講 義を思い出しながら自分で読んでくだ さい。