ホールの結婚定理

数学において、フィリップ・ホール(1935)によって証明されたホールの結婚定理は、2 つの同等の定式化を持つ定理です。いずれの場合も、定理はオブジェクトが存在するための必要かつ十分な条件 を示します。

• 組み合わせ論的定式化は、有限集合に横断性があるかどうか、つまり各集合から重複なく要素を選択できるかどうかの答えを示します。ホールの条件は、集合の任意の集合グループについて、そこに含まれる一意の要素の合計が、グループ内の集合の数以上であることです。
• グラフ理論の定式化は、有限二部グラフに完全マッチング、つまり、あるグループの各頂点を他のグループの隣接する頂点に一意にマッチングさせる方法があるかどうかに答えます。ホールの条件は、あるグループの頂点の任意のサブセットに、等しいかそれ以上のサイズの近傍があることです。

を有限集合族とします（自体は無限であってはならないが、 に含まれる集合は無限であってもよく、同じ集合 を複数回含む場合があることに注意）。^[1]を に含まれるすべての集合の和集合、つまり のうちの少なくとも 1 つの集合に属する要素の集合とします。 の横断とは、に含まれる各集合から異なる要素を 1 つ選択することで得られる の部分集合です。この概念は、横断を各 に対して となるような単射関数の像として定義することで形式化できます。横断の別名は、異なる代表のシステムです。 ${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle X}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle X}$${\displaystyle {\mathcal {F}}}$ ${\displaystyle f:{\mathcal {F}}\to X}$${\displaystyle f(S)\in S}$${\displaystyle S\in {\mathcal {F}}}$

の各サブファミリーに、その集合の数と同数以上の異なるメンバーが含まれる場合、コレクションは結婚条件を満たします。つまり、すべての に対して、 横断線が存在する場合、結婚条件は必ず成り立ちます。横断線を定義するために使用される 関数は、その和集合 のサブセットにマップされ、そのサイズは に等しいため、和集合全体は少なくとも同じ大きさである必要があります。ホールの定理によれば、逆も成り立ちます。 ${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {G}}\subseteq {\mathcal {F}}}$$${\displaystyle |{\mathcal {G}}|\leq {\Bigl |}\bigcup _{S\in {\mathcal {G}}}S{\Bigr |}.}$$${\displaystyle f}$${\displaystyle {\mathcal {G}}}$${\displaystyle |{\mathcal {G}}|}$

例1

およびを含む族について考えます。横断線は、をに、 をにマップする関数、またはを をに、を にマップする関数によって生成できます。や などの他の横断線もあります。この族には少なくとも 1 つの横断線があるため、結婚条件が満たされます。 のすべてのサブ族は、マップ先の代表の集合とサイズが等しく、サブ族の和集合のサイズ以下です。${\displaystyle {\mathcal {F}}=\{A_{1},A_{2},A_{3}\}}$${\displaystyle X=\{1,2,3,4,5\}}$$${\displaystyle {\begin{aligned}A_{1}&=\{1,2,3\}\\A_{2}&=\{1,4,5\}\\A_{3}&=\{3,5\}.\\\end{aligned}}}$$${\displaystyle \{1,3,5\}}$${\displaystyle A_{1}}$${\displaystyle 1}$${\displaystyle A_{2}}$${\displaystyle 5}$${\displaystyle A_{3}}$${\displaystyle 3}$${\displaystyle A_{1}}$${\displaystyle 3}$${\displaystyle A_{2}}$${\displaystyle 1}$${\displaystyle A_{3}}$${\displaystyle 5}$${\displaystyle \{1,2,3\}}$${\displaystyle \{1,4,5\}}$${\displaystyle {\mathcal {F}}}$

例2

を考察します。有効な横断は存在しません。サブファミリー によって示されるように、結婚条件は破られます。ここで、サブファミリー内の集合の数は ですが、3 つの集合の和集合には2 つの要素のみが含まれます。${\displaystyle {\mathcal {F}}=\{A_{1},A_{2},A_{3},A_{4}\}}$$${\displaystyle {\begin{aligned}A_{1}&=\{2,3,4,5\}\\A_{2}&=\{4,5\}\\A_{3}&=\{5\}\\A_{4}&=\{4\}.\\\end{aligned}}}$$${\displaystyle {\mathcal {G}}=\{A_{2},A_{3},A_{4}\}}$${\displaystyle |{\mathcal {G}}|=3}$${\displaystyle A_{2}\cup A_{3}\cup A_{4}=\{4,5\}}$

与えられた有限サイズの族が持つ可能性のある横断線の異なる数の下限は、次のようにして得られます。 の各集合の濃度が である場合、 の異なる横断線の数は であれば、 であれば となります。^[2]${\displaystyle {\mathcal {F}}}$${\displaystyle n}$${\displaystyle {\mathcal {F}}}$${\displaystyle \geq r}$${\displaystyle {\mathcal {F}}}$${\displaystyle r!}$${\displaystyle r\leq n}$${\displaystyle r(r-1)\cdots (r-n+1)}$${\displaystyle r>n}$

族の横断は順序付けられたシーケンスであるため、2 つの異なる横断がまったく同じ要素を持つ可能性があることを思い出してください。たとえば、コレクション には、異なる横断として と があります。${\displaystyle {\mathcal {F}}}$${\displaystyle A_{1}=\{1,2,3\}}$${\displaystyle A_{2}=\{1,2,5\}}$${\displaystyle (1,2)}$${\displaystyle (2,1)}$

を、二部集合と、辺集合 を持つ有限二部グラフとします。-完全マッチング( -飽和マッチングとも呼ばれる) は、 内のすべての頂点をカバーするマッチング、つまり互いに素な辺の集合です。 ${\displaystyle G=(X,Y,E)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle E}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$

の部分集合について、における の近傍、つまり の少なくとも 1 つの要素に隣接する 内のすべての頂点の集合を で表します。この定式化における結婚定理は、のすべての部分集合に対して次の場合のみ、 -完全マッチングが存在することを述べています。つまり、 のすべての部分集合には、 内に十分な数の近傍が存在する必要があります。 ${\displaystyle W}$${\displaystyle X}$${\displaystyle N_{G}(W)}$${\displaystyle W}$${\displaystyle G}$${\displaystyle Y}$${\displaystyle W}$${\displaystyle X}$${\displaystyle W}$${\displaystyle X}$$${\displaystyle |W|\leq |N_{G}(W)|.}$$${\displaystyle W}$${\displaystyle X}$${\displaystyle Y}$

-完全マッチングでは、 に接続するすべての辺が内の の異なる隣接辺に接続するため、これらのマッチングした隣接辺の数は少なくとも になります。 のすべての隣接辺の数は少なくとも と同じくらい大きくなります。 ${\displaystyle X}$${\displaystyle M}$${\displaystyle W}$${\displaystyle W}$${\displaystyle Y}$${\displaystyle |W|}$${\displaystyle W}$

逆説を考えてみましょう。完全なマッチングがない場合は、少なくとも 1 つの についてホールの条件に違反している必要があります。を最大マッチングとし、 を内のマッチしない任意の頂点とします。から始まるすべての交互パス（ の外側と内側のエッジを交互に使用する 内のパス）を考えます。を（それ自体を含む）に属するこれらのパスの頂点の集合とし、を に属するこれらのパスの頂点の集合とします。すると、 内のすべての頂点はによって内の頂点とマッチングします。これは、マッチしない頂点への交互パスを使用して、その各エッジが に属するかどうかを切り替えることで、マッチングのサイズを増やすことができるためです。したがって、 のサイズは、のこれらのマッチした隣接頂点の数に、マッチしない頂点 1 を加えた数以上になります。つまり、 です。しかし、すべての頂点 に対して、のすべての隣接頂点は に属します。 への交互パスは、への交互パスから一致するエッジを削除するか、への交互パスに一致しないエッジを追加することによって見つけることができます。したがって、であり、ホールの条件が違反されていることを示しています。 ${\displaystyle X}$${\displaystyle W\subseteq X}$${\displaystyle M}$${\displaystyle u}$${\displaystyle X}$${\displaystyle G}$${\displaystyle M}$${\displaystyle u}$${\displaystyle W}$${\displaystyle X}$${\displaystyle u}$${\displaystyle Z}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle M}$${\displaystyle W}$${\displaystyle M}$${\displaystyle W}$${\displaystyle |Z|}$${\displaystyle Z}$${\displaystyle u}$${\displaystyle |W|\geq |Z|+1}$${\displaystyle v\in W}$${\displaystyle w}$${\displaystyle v}$${\displaystyle Z}$${\displaystyle w}$${\displaystyle vw}$${\displaystyle v}$${\displaystyle vw}$${\displaystyle v}$${\displaystyle Z=N_{G}(W)}$${\displaystyle |W|\geq |N_{G}(W)|+1}$

和集合の有限族によって定義される組合せ論的定式化の問題は、各辺が 内の集合をその集合の要素に接続する二部グラフに変換できます。このグラフの -完全マッチングは、 の一意の代表のシステムを定義します。逆に、任意の二部グラフから、 内の頂点の近傍の族である、集合の有限族を定義できます。この族の一意の代表の任意のシステムは、 内の -完全マッチングに対応します。このように、有限集合の有限族の組合せ論的定式化と有限グラフのグラフ理論的定式化は同等です。 ${\displaystyle {\mathcal {F}}}$${\displaystyle X}$${\displaystyle G=({\mathcal {F}},X,E)}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle G=(X,Y,E)}$${\displaystyle X}$${\displaystyle X}$${\displaystyle G}$

同じ同値性は、有限集合の無限族および特定の無限グラフにも適用されます。この場合、各集合が有限であるという条件は、二部グラフでは 内のすべての頂点が有限次数を持つという条件に対応します。 内の頂点の次数は制約されません。 ${\displaystyle G=(X,Y,E)}$${\displaystyle X}$${\displaystyle Y}$

ホールの定理は、シュペルナーの補題に基づいて（非構成的に）証明することができる。^{[3] ：Thm.4.1、4.2}

この定理には多くの応用がある。例えば、標準的なトランプのデッキが4枚ずつ13の山に分かれて配られた場合、結婚定理によれば、各山から1枚のカードを選んで、そのカードに各ランク（エース、2、3、...、クイーン、キング）のカードが1枚ずつ含まれるようにすることができる。これは、1つのパーティションに13の山を、もう1つのパーティションに13のランクを含む2部グラフを構築することで実現できる。残りの証明は結婚条件から得られる。より一般的には、任意の正則2部グラフは完全マッチングを持つ。^{[4] : 2}

より抽象的に、を群、をの有限指数部分群とします。すると、結婚定理を用いて、における の左剰余類の集合と右剰余類の集合の両方に対して横断的となるような集合が存在することが示されます。^[5]${\displaystyle G}$${\displaystyle H}$ ${\displaystyle G}$${\displaystyle T}$${\displaystyle T}$${\displaystyle H}$${\displaystyle G}$

結婚定理は、ラテン長方形はのとき常にラテン長方形に拡張でき、最終的にはラテン方陣に拡張できるという事実の通常の証明に使用されます。^[6]${\displaystyle r\times n}$ ${\displaystyle (r+1)\times n}$${\displaystyle r<n}$

この定理は、組み合わせ論における非常に強力な定理の集合の一部であり、これらの定理はすべて、第一原理から証明するよりも、他の定理からこれらの定理の 1 つを証明する方が簡単であるという点で、非公式な意味で互いに関連しています。これらの定理には次のものが含まれます。

• ケーニッヒ・エゲルヴァーリの定理( 1931 ) (デネス・ケーニッヒ、イェンシュ・エゲルヴァーリ)
• ケーニッヒの定理^[7]
• メンガーの定理(1927)
• 最大フロー最小カット定理（フォード・フルカーソンアルゴリズム）
• バーコフ・フォン・ノイマンの定理(1946)
• ディルワースの定理。

特に、^{[8] [9]}には、ディルワースの定理 ─ ホールの定理 ─ ケーニッヒ・エゲルヴァーリの定理 ─ ケーニッヒの定理の含意に関する簡単な証明がある。

フィリップ・ホールの元の証明を注意深く調べることで、マーシャル・ホール・ジュニア（フィリップ・ホールとは無関係）は、証明が無限大に対しても機能するように結果を微調整することができました。^[10]この変形はフィリップ・ホールの結婚定理を拡張したものです。 ${\displaystyle {\mathcal {F}}}$

が、必ずしも区別される必要のない有限集合の（おそらく無限の）族であるとすると、 が結婚条件を満たす 場合のみ、 は横断を持ちます。${\displaystyle {\mathcal {F}}=\{A_{i}\}_{i\in I}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$

Marshall Hall Jr. による次の例は、結婚条件が、無限集合が許容される無限族における横断線の存在を保証しないことを示しています。

を家族、とする。この無限家族に対して結婚条件は成立するが、横断構造は構築できない。^[11]${\displaystyle {\mathcal {F}}}$${\displaystyle A_{0}=\mathbb {N} }$${\displaystyle A_{i}=\{i-1\}}$${\displaystyle i\geq 1}$

マーシャル・ホールの結婚定理の拡張のグラフ理論的定式化は、次のように述べることができる。辺AとB を持つ二部グラフが与えられたとき、グラフ内でBの部分集合CがAの部分集合Dのサイズより小さいか等しいとは、グラフ内でCからDへの注入（つまり、グラフの辺のみを使用して）が存在する場合であり、さらにグラフ内で反対方向の注入が存在しない場合は、グラフ内で厳密に小さいという。グラフ内で省略すると、基数を比較するという通常の概念になる点に注意すること。無限結婚定理は、グラフ内でN ( C ) がCより厳密に小さいAの部分集合Cが存在しない場合に限り、グラフ内でAからBへの注入が存在することを述べている。^[12]

空でない集合の集合（集合の数や集合のサイズに制限はありません）のそれぞれから（必ずしも異なるとは限らない）要素を選択するという、より一般的な問題は、選択公理が受け入れられる場合にのみ一般に許可されます。

グラフにおける分数マッチングとは、各辺に非負の重みを割り当て、各頂点に隣接する重みの合計が最大で1になるようにすることです。分数マッチングは、各頂点に隣接する重みの合計がちょうど1である場合にX完全です。以下は、2部グラフG = ( X+Y, E )に対して同等です。^[13]

• G はX 完全マッチングを許容します。
• G はX 完全分数マッチングを許容します。この意味は、X完全マッチングがX完全分数マッチングの特殊なケースであり、各重みが 1 (エッジがマッチング内にある場合) または 0 (そうでない場合) であるという事実から直接導かれます。
• G はホールの結婚条件を満たしています。この含意は、 Xの各部分集合Wについて、 Wの頂点付近の重みの合計が| W | であるため、それらに隣接する辺は必ずYの少なくとも|W|頂点に隣接しているために成り立ちます。

ホールの条件が成立しない場合、元の定理は完全なマッチングが存在しないということだけを示し、存在する最大のマッチングが何かは示しません。この情報を知るには、グラフの欠陥という概念が必要です。二部グラフG = ( X + Y , E ) が与えられた場合、X に関する G の欠陥は、 Xのすべての部分集合Wにわたる差 | W | - | N _G ( W )| の最大値です。欠陥が大きいほど、グラフはホールの条件を満たすことから遠ざかります。

ホールの結婚定理を用いると、二部グラフGの欠陥がdである場合、G は少なくとも | X |- dのサイズのマッチングを許容することが証明できます。

• 一般的なグラフ（必ずしも二部グラフではない）における完全マッチングの特徴付けは、Tutte の定理によって提供されます。
• ホールの定理の二部ハイパーグラフへの一般化は、ハイパーグラフに対するさまざまなホール型定理によって提供されます。

• Brualdi, Richard A. (2010)、Introductory Combinatorics、アッパーサドルリバー、ニュージャージー州：Prentice-Hall/Pearson、ISBN 978-0-13-602040-0
• キャメロン、ピーター J. (1994)、組合せ論: トピック、テクニック、アルゴリズム、ケンブリッジ: ケンブリッジ大学出版局、ISBN 978-0-521-45761-3
• ホール、マーシャル・ジュニア（1986年）、組合せ理論（第2版）、ニューヨーク：ジョン・ワイリー・アンド・サンズ、ISBN 978-0-471-09138-7
• ホール、フィリップ(1935)、「部分集合の代表について」、J. ロンドン数学協会、10 (1): 26–30、doi :10.1112/jlms/s1-10.37.26
• ハルモス、ポール R. ; ヴォーン、ハーバート E. (1950)、「結婚問題」、アメリカ数学誌、72 (1): 214–215、doi :10.2307/2372148、JSTOR  2372148、MR  0033330
• ライヒマイダー、PF（1984）、いくつかの組み合わせマッチング定理の同値性、ポリゴン出版社、ISBN 978-0-936428-09-3
• フレッド・S・ロバーツ; Tesman、Barry (2009)、Applied Combinatorics (第 2 版)、ボカラトン: CRC Press、ISBN 978-1-4200-9982-9
• van Lint, JH; Wilson, RM (1992)、A Course in Combinatorics、ケンブリッジ：ケンブリッジ大学出版局、ISBN 978-0-521-42260-4

• 結婚の定理
• cut-the-knotにおける結婚定理とアルゴリズム
• ホールの結婚定理がラッキーのノートで直感的に説明されています。

この記事には、Creative Commons Attribution-Share-Alike Licenseに基づいてライセンスされているPlanetMathの Hall の結婚定理の証明からの資料が組み込まれています。