ホールの定理

ホールの定理または結婚定理は、組合せ数学の帰結の1つで、有限集合の集まりのそれぞれから別個の元を選択できる条件を与える。名称の由来は数学者のフィリップ・ホール。

1. 定義と表現
--------

//S// = {//S////1//, //S////2//, ... } が有限集合の集まりとする。//S//の横断集合  または //S// の完全代表系  とは、別個の元からなる集合 //X// = {//x////1//, //x////2//, ...}で、全ての //i// について //x////i//∈//S////i// となっている集合である。

//S//の結婚条件  とは、//S//の任意の部分集合 についての次の条件である。

ここで、|//T//| は集合 //T//の元の数を意味する。

ホールの定理は、SDR //X// が存在することと、//S// が結婚条件を満たすことは同値であるというものである。

2. 議論と例
-------

例 1: //S// = {//S////1//, //S////2//, //S////3//} があり、それぞれは以下の通り。

//S////1// = {1, 2, 3}//S////2// = {1, 4, 5}//S////3// = {3, 5}妥当なSDRは {1, 4, 5} である。

例 2: //S// = {//S////1//, //S////2//, //S////3//, //S////4//} があり、それぞれは以下の通り。

//S////1// = {2, 3, 4, 5}//S////2// = {4, 5}//S////3// = {5}//S////4// = {4}妥当なSDRは存在しない。また、部分集合 {//S////2//, //S////3//, //S////4//} について結婚条件が成り立たない。

結婚定理の一般的応用例は、//n//人の男性と//n//人の女性という2つのグループを想定する。それぞれの女性は男性の部分集合のいずれかと結婚できれば幸せである。また、それぞれの男性は自分と結婚したいと思っている女性と結婚できれば幸せである。ここで、全員が幸せになるような組合せは可能か、という問題である。

ここで //S////i// を //i//番目の女性が結婚して幸せになれる男性の集合とする。結婚定理によれば、それぞれの女性が男性と幸せな結婚をできることと、集合の集まり {//S////1//, //S////2//, ...} が結婚条件を満たすことは同値である。

なお、この場合の結婚条件とは、女性の任意の部分集合 について、結婚したら幸せだという女性が少なくとも1人以上いる男性の数 がその部分集合に含まれる女性の人数 以上でなければならない。これが成り立たないと結婚対象となる男性の人数が足りないことを意味するので、この条件が必要条件であることは明らかである。興味深いことに、これは同時に十分条件でもある。

この定理は結婚以外にもいろいろな場面に応用できる。例えば、52枚のトランプを4枚ずつ13の山に分けるとする。結婚定理をこれに適用すると、それぞれの山から1枚ずつカードを選んで、エースからキングまでの13枚を必ず揃えることができるといえる。

より抽象的な例としては、ある群 //G// があり、//H// を //G// の有限な部分群とする。これに結婚定理を適用すると、//G// における //H// の左剰余類の集合と右剰余類の集合のSDRであるような集合 //X// が必ず存在するといえる。

より一般的問題として、集合の集まりがあったときにそれぞれの集合から元を選ぶことができるには、選択公理が成り立たなければならない。

3. グラフ理論
--------

結婚定理はグラフ理論にも応用される。グラフ理論の用語で問題を表すと次のようになる。

有限な2部グラフ //G//:=  で //X// と //Y// が同じ大きさとしたとき、マッチングは存在するか? すなわち、//G// の各頂点が必ず1つの辺と接合するような辺の集合は存在するか?

結婚定理がこの問題の答えを与える。

//G// の頂点の集合 //W// について、//G// における //W// の近傍を で表す。近傍とは、//W// の何らかの元に隣接する全頂点の集合である。グラフ理論における結婚定理によれば、完全マッチングが存在することと //X// のあらゆる部分集合 //W// について次が成り立つことは同値である。

言い換えれば、//X// のあらゆる部分集合 //W// は //Y// に属する頂点と十分に隣接している。

任意のグラフに一般化したものがタットの定理である。

3.1. より一般化した表現
--------------

有限2部グラフ //G//:=  で //X// と //Y// は同じ大きさでなくともよい。ここで、//G// の最大マッチングの端点が//X//をすべて覆うことと、//X// の全ての部分集合 //W// について次が成り立つことは同値である。

4. グラフ理論による証明
-------------

まず、2部グラフ //G// =  = //G// が //X//-飽和マッチングを持つならば、任意の//W// ⊆ //X// に対して|N//G//| ≥ |//W// |であることを示す。

Mを//X//-飽和マッチングとする。 このとき、Mによって、与えられた//W// ⊆ //X// とマッチングされている//Y// の頂点集合をMと書くと、マッチングの定義より|M|=|//W// |。 しかし、Mの全ての元は//W// の近傍に属するので、M ⊆ N//G//である。 よって、 |N//G//| ≥ |M| であるから、|N//G//| ≥ |//W// |。

次に、任意の//W// ⊆ X に対して|N//G//| ≥ |//W// | ならば、//G//は//X//-飽和マッチングを持つことを示す。

2部グラフ//G//が//X//-飽和マッチングを持たないと仮定して矛盾を導く。//M// を//G//の最大マッチングすると、//M//-非飽和点が存在するので、これを//u// ∈ //X// とする。//u// を始点とする任意の//M//-交互道を考え、この交互道によって//u//と接続するすべての//Y// の頂点の集合を//T// とする。 同様に、//u//と接続するすべての//X// の頂点の集合を//W// とする。//u// を始点とする//M//-交互道の終点が、//Y//に属する点となることはない。

ここで、//T// に属する全ての頂点は、Mにより//W// の頂点とマッチングされており、 逆に全ての頂点 //v// ∈ //W// \ {//u//} はMにより//T// の頂点とマッチングされているので、 M は //W// \ {//u//} と //T// の間の全単射を与える。よって、 |//W// | = |//T// | + 1であり、N//G// ⊇ //T// が成立する。 他方、//v// ∈ //Y// を//w// ∈ //W// に接続される頂点としたとき、辺  が Mに属していれば、//v// ∈ //T//。 そうでなければ、辺  を通る//M//-交互道を構成できるので、//v// ∈ //T//となり、N//G// ⊆ //T//が成立。 したがって、 |N//G//| = |//T// | = |//W// | − 1 となり、矛盾。

5. 論理的に等価な定理
------------

この定理は組合せ数学における非常に強力な一連の定理の1つである。それらの定理は形式的でない意味で互いに関連しており、いずれかの定理に基づいて別の定理を容易に導ける。これには以下のような定理が含まれる。

König's theorem
Konig-Egervary theorem  
メンガーの定理 
最大フロー最小カット定理
バーコフ・フォン・ノイマンの定理 
Dilworth's theorem特に Dilworth's theorem ⇒ ホールの定理 ⇔ Konig-Egervary theorem ⇔ König's theorem という関係を導く単純な証明が存在する。

6. 脚注・出典
--------

7. 外部リンク
--------

[1] at cut-the-knot
[2] at cut-the-knot
[3] PlanetMath