Теорема Холла

Теорема Холла (також відома як теорема про одруження)— комбінаторне твердження, що дає достатні і необхідні умови існування вибору різних елементів з деякого набору скінченних множин. Теорема названа на честь англійського математика Філіпа Холла.

Твердження

Теорема Холла може бути сформульована кількома способами, зокрема за допомогою мови теорії графів і теорії трансверсалів.

Твердження у теорії графів

Нехай $G=(V,E)\;$ — деякий граф, і $A\subseteq V,B\subseteq V\;$ підмножини його вершин, такі що $A\cup B=V\;$, і для довільного ребра $e\;$ такого що $e=\lbrace v,u\rbrace \;$, справедливе твердження

$(v\in A\land u\in B)\lor (v\in B\land u\in A)\;$,

тобто граф $G\;$ є двочастковим. Тоді для даного графа існує набір ребер, що з'єднують вершини $A\;$ з різними вершинами $B\;$ тоді й лише тоді коли для кожної підмножини елементів $K\subseteq A\;$ виконується

$|W|\geqslant |K|,\;$

де:

$W=\{w\in B\colon (\exists k\in K)\lbrace k,w\rbrace \in E\}\;$

множина елементів з $B,\;$ що з'єднані ребрами хоча б з одним елементом підмножини $K\;$ Остання умова також називається умовою одружень.

Твердження у теорії трансверсалів

Нехай S = {S₁, S₂, … } — деяка сім'я скінченних множин. Трансверсалем для S, називається множина X = {x₁, x₂, …} різних елементів (де |X| = |S|) з властивістю, що для всіх i, x_i∈S_i.

Теорема Холла стверджує, що трансверсаль для S існує тоді й лише тоді, коли виконується умова

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

Доведення

Доведення 1

Доведення здійснюватимемо методом математичної індукції щодо кількості елементів S.

Теорема очевидно справедлива для $\vert S\vert =0$. Припустимо твердження теореми справедливе для $\left\vert S\right\vert <n$, доведемо її для випадку $\left\vert S\right\vert =n$.

Спершу розглянемо випадок коли виконується $\left\vert \cup T\right\vert \geq \left\vert T\right\vert +1$ для всіз власних підмножин T of S. Виберемо довільний елемент $x\in S_{n}$ представником $S_{n}.$ Якщо існує трансверсаль для $S'=\left\{S_{1}\setminus \{x\},\ldots ,S_{n-1}\setminus \{x\}\right\}$, тоді $R'\cup \{x\}$ є трансверсаллю для S. Але якщо взяти $\{S_{j_{1}}\setminus \{x\},...,S_{j_{k}}\setminus \{x\}\}=T'\subseteq S'$ то за припущенням, $\left\vert \cup T'\right\vert \geq \left\vert \cup _{i=1}^{k}S_{j_{i}}\right\vert -1\geq k$. Згідно з припущенням індукції для $S'$ і як наслідок для $S$ існує трансверсаль.

В іншому випадку для деякої $\emptyset \neq T\subset S$ виконується рівність $\left\vert \cup T\right\vert =\left\vert T\right\vert$. Для $T$ маємо, що для кожної $T'\subseteq T\subset S$ виконується $\left\vert \cup T'\right\vert \geq \left\vert T'\right\vert$, і за припущенням індукції для $T$ існує трансверсаль.

Для завершення доведення достатньо знайти представників для множин $S\setminus T$ що не містять елементів $\cup T$. Для цього достатньо довести, що для довільної множини $T'\subseteq S\setminus T$, виконується

$\left\vert \cup T'\setminus \cup T\right\vert \geq \left\vert T'\right\vert$

і скористатися припущенням індукції.

Маємо

$\left\vert \cup T'\setminus \cup T\right\vert$

$=\left\vert \bigcup (T\cup T')\right\vert -\left\vert \cup T\right\vert \geq \left\vert T\cup T'\right\vert -\left\vert T\right\vert$

$=\left\vert T\right\vert +\left\vert T'\right\vert -\left\vert T\right\vert =\left\vert T'\right\vert$,

зважаючи на відсутність спільних елементів у $T$ і $T'$, і той факт, що $\left\vert \cup T\right\vert =\left\vert T\right\vert$. Тому за припущенням індукції, $S\setminus T$ має трансверсаль, що не містить елементів $\cup T$.

Доведення 2

Позначимо через $H\;$ підграф графа $G=(V,E)\;$ такий, що

• кожна вершина інцидентна деякому ребру графа $H\;$
• граф $H\;$ задовольняє умову одружень і є мінімальним за включенням ребер графом, що задовольняє цю вимогу.

Позначимо $d_{H}(a)\;$ — степінь вершини a в графі $H\;$. Очевидно, що $d_{H}(a)\geq 1$. Для доведення теореми Холла достатньо довести, що $d_{H}(a)=1\;$.

Для цього спершу позначимо : $N_{H}(K)=\{w\in B\colon (\exists k\in K)\lbrace k,w\rbrace \in E\}\;$

Припустимо, що деяка вершини $a\in A$ з'єднується більш ніж з однією вершиною і нехай$b_{1},b_{2}\in N_{H}(a).\;$ Тоді згідно з вибором $H\;$ графи $H-\{ab_{1}\}\;$ і $H-\{ab_{2}\}\;$ не задовольняють умови одружень. Тому для $i=1,2\;$ існують такі $A_{i}\subset A$ що містять a і $|A_{i}|>|B_{i}|\;$ де $B_{i}:=N_{H-\{ab_{i}\}}(A_{i})\;$. Звідси одержуємо:

$|N_{H}(A_{1}\cap A_{2}\smallsetminus \{a\})|\leq |B_{1}\cap B_{2}|$

$=|B_{1}|+|B_{2}|-|B_{1}\cup B_{2}|=|B_{1}|+|B_{2}|-|N_{H}(A_{1}\cup A_{2})$

$\leq |A_{1}|-1+|A_{2}|-1-|A_{1}\cup A_{2}|=|A_{1}\cap A_{2}\smallsetminus \{a\}|-1$

Тобто H не задовольняє умови одружень, що суперечить припущенню і доводить теорему.

Посилання

• Теорема Холла на сайті cut-the-knot [Архівовано 3 листопада 2009 у Wayback Machine.]
• Теорема і алгоритм [Архівовано 3 червня 2010 у Wayback Machine.]
• Джозеф Ротман. An Introduction to the Theory of Groups. — 4th. — Springer (Graduate Texts in Mathematics), 1994. — 532 с. — ISBN 978-0387942858.(англ.)