ホールの定理

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

定義と表現

S = {S₁, S₂, ... } が有限集合の集まりとする（可算である必要はない）。Sの横断集合 (transversal) または S の system of distinct representatives (SDR) とは、別個の元からなる集合 X = {x₁, x₂, ...}（ここで |X| = |S|）で、全ての i について x_i∈S_i となっている集合である。

Sの結婚条件 (marriage condition) とは、Sの任意の部分集合 $T\subseteq S$ についての次の条件である。

$|T|\leq {\Bigl |}\bigcup _{A\in T}A{\Bigr |}$

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

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

議論と例

例 1: S = {S₁, S₂, S₃} があり、それぞれは以下の通り。

S₁ = {1, 2, 3}

S₂ = {1, 4, 5}

S₃ = {3, 5}

妥当なSDRは {1, 4, 5} である（ただし、これは唯一のSDRではない。例えば {2, 1, 3} でもよい）。

例 2: S = {S₁, S₂, S₃, S₄} があり、それぞれは以下の通り。

S₁ = {2, 3, 4, 5}

S₂ = {4, 5}

S₃ = {5}

S₄ = {4}

妥当なSDRは存在しない。また、部分集合 {S₂, S₃, S₄} について結婚条件が成り立たない。

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

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

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

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

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

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

グラフ理論

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

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

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

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

$|X|\leq |N_{G}(X)|$

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

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

より一般化した表現

有限2部グラフ G:= (S + T, E) で S と T は同じ大きさでなくともよい。ここで、G が S の T へのマッチングを含むことと、S の全ての部分集合 X について次が成り立つことは同値である。

$|X|\leq |N_{G}(X)|$

論理的に等価な定理

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

• König's theorem
• Konig-Egervary theorem (1931) (Dénes Kőnig, Jenő Egerváry)
• メンガーの定理 (1927)
• 最大フロー最小カット定理
• Birkhoff-Von Neumann theorem (1946)
• Dilworth's theorem

特に Dilworth's theorem ⇒ ホールの定理 ⇔ Konig-Egervary theorem ⇔ König's theorem という関係を導く単純な証明が存在する。

外部リンク

• Marriage Theorem at cut-the-knot
• Marriage Problem at cut-the-knot
• proof of Hall's marriage theorem PlanetMath