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

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

Твердження

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

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

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

$(v\in A\wedge u\in B)\vee (v\in B\wedge u\in A)$,

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

$|W|⩾|K|,$

де:

$W=\{w\in B:(\mathrm{\exists }k\in K)\{k,w\}\in E\}$

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

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

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

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

$|T|\le \left|\bigcup _{t\in T}t\right|$

Доведення

Доведення 1

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

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

Спершу розглянемо випадок коли виконується $|\cup T|\ge \left|T\right|+1$ для всіз власних підмножин T of S. Виберемо довільний елемент $x\in S_n$ представником $S_n.$ Якщо існує трансверсаль для $S^{\prime }=\{S_1\setminus \{x\},\dots ,S_{n-1}\setminus \{x\}\}$, тоді $R^{\prime }\cup \{x\}$ є трансверсаллю для S. Але якщо взяти $\{S_{j_1}\setminus \{x\},...,S_{j_k}\setminus \{x\}\}=T^{\prime }\subseteq S^{\prime }$ то за припущенням, $|\cup T^{\prime }|\ge \left|\underset{i=1}{\overset{k}{\cup }}{S}_{j_i}\right|-1\ge k$. Згідно з припущенням індукції для $S^{\prime }$ і як наслідок для $S$ існує трансверсаль.

В іншому випадку для деякої $\mathrm{\varnothing }\ne T\subset S$ виконується рівність $|\cup T|=\left|T\right|$. Для $T$ маємо, що для кожної $T^{\prime }\subseteq T\subset S$ виконується $|\cup T^{\prime }|\ge \left|T^{\prime }\right|$, і за припущенням індукції для $T$ існує трансверсаль.

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

$|\cup T^{\prime }\setminus \cup T|\ge \left|T^{\prime }\right|$

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

Маємо

$|\cup T^{\prime }\setminus \cup T|$

$=|\bigcup (T\cup T^{\prime })|-|\cup T|\ge |T\cup T^{\prime }|-\left|T\right|$

$=\left|T\right|+\left|T^{\prime }\right|-\left|T\right|=\left|T^{\prime }\right|$,

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

Доведення 2

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

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

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

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

Припустимо, що деяка вершини $a\in A$ з'єднується більш ніж з однією вершиною і нехай$b_1,b_2\in N_H(a).$ Тоді згідно з вибором $H$ графи $H-\{a{b}_1\}$ і $H-\{a{b}_2\}$ не задовольняють умови одружень. Тому для $i=1,2$ існують такі $A_i\subset A$ що містять a і $|A_i|>|B_i|$ де $B_i:=N_{H-\{a{b}_i\}}(A_i)$. Звідси одержуємо:

$|N_H(A_1\cap A_2\setminus \{a\})|\le |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)$

$\le |A_1|-1+|A_2|-1-|A_1\cup A_2|=|A_1\cap A_2\setminus \{a\}|-1$

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

Посилання

• Теорема Холла на сайті cut-the-knot Шаблон:Webarchive
• Теорема і алгоритм Шаблон:Webarchive
• Шаблон:Rotman.An Introduction to the Theory of Groups