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

Результат в комбинаторике и теории графов

В математике теорема Холла о браке , доказанная Филиппом Холлом (1935), представляет собой теорему с двумя эквивалентными формулировками. В каждом случае  теорема дает необходимое и достаточное условие для существования объекта:

• Комбинаторная формулировка отвечает на вопрос, имеет ли конечный набор множеств трансверсаль — то есть, можно ли выбрать элемент из каждого набора без повторения. Условие Холла заключается в том, что для любой группы множеств из набора общее число уникальных элементов, которые они содержат, по крайней мере так же велико, как и количество множеств в группе.
• Теоретико -графовая формулировка отвечает на вопрос, имеет ли конечный двудольный граф идеальное соответствие — то есть способ сопоставить каждую вершину из одной группы уникальным образом со смежной вершиной из другой группы. Условие Холла заключается в том, что любое подмножество вершин из одной группы имеет соседство равного или большего размера.

Комбинаторная формулировка

Заявление

Пусть будет конечным семейством множеств (обратите внимание, что хотя само по себе не может быть бесконечным, множества в нем могут быть таковыми и могут содержать одно и то же множество несколько раз ). ^[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}}|}$

Теорема Холла о браке  —  Семейство конечных множеств имеет трансверсаль тогда и только тогда, когда удовлетворяет условию брака. ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

Примеры

пример 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, нарушено условие брака

Пример 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}$

Напомним, что трансверсаль для семейства — это упорядоченная последовательность, поэтому две разные трансверсали могут иметь совершенно одинаковые элементы. Например, коллекция , имеет и в качестве различных трансверсалей. ${\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}$

Для подмножества , пусть обозначает окрестность в , множество всех вершин в , которые смежны хотя бы с одним элементом из . Теорема о браке в этой формулировке утверждает, что существует -совершенное паросочетание тогда и только тогда, когда для каждого подмножества : Другими словами, каждое подмножество должно иметь достаточно много соседей в . ${\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}$

Достаточность

Рассмотрим контрапозицию : если нет -совершенного соответствия, то условие Холла должно быть нарушено по крайней мере для одного . Пусть будет максимальным соответствием, и пусть будет любой несовпадающей вершиной в . Рассмотрим все чередующиеся пути (пути в , которые попеременно используют ребра снаружи и внутри ), начиная с . Пусть будет множеством вершин в этих путях, которые принадлежат (включая себя), и пусть будет множеством вершин в этих путях, которые принадлежат . Тогда каждая вершина в сопоставлена ​​с вершиной в , потому что чередующийся путь к несовпадающей вершине может быть использован для увеличения размера соответствия путем переключения того, принадлежит ли каждое из ее ребер или нет. Следовательно, размер равен по крайней мере числу этих сопоставленных соседей , плюс один для несовпадающей вершины . То есть, . Однако для каждой вершины каждый сосед принадлежит : альтернативный путь к можно найти либо удалив сопоставленное ребро из альтернативного пути к , либо добавив не сопоставленное ребро к альтернативному пути к . Следовательно, и , показывая, что условие Холла нарушается. ${\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] : Теор.4.1, 4.2}

Приложения

Теорема имеет множество приложений. Например, для стандартной колоды карт , разложенной на 13 стопок по 4 карты в каждой, теорема о женитьбе подразумевает, что можно выбрать одну карту из каждой стопки так, чтобы выбранные карты содержали ровно одну карту каждого ранга (туз, 2, 3, ..., дама, король). Это можно сделать, построив двудольный граф с одним разделом, содержащим 13 стопок, и другим разделом, содержащим 13 рангов. Оставшееся доказательство следует из условия женитьбы. В более общем смысле, любой регулярный двудольный граф имеет идеальное паросочетание. ^{[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}$

Логические эквивалентности

Эта теорема является частью коллекции чрезвычайно мощных теорем комбинаторики, все из которых связаны друг с другом неформальным образом, поскольку проще доказать одну из этих теорем из другой, чем из первых принципов. К ним относятся:

• Теорема Кенига -Эгервари (1931) ( Денес Кениг , Йенё Эгервари )
• Теорема Кёнига ^[7]
• Теорема Менгера (1927)
• Теорема о максимальном потоке и минимальном разрезе (алгоритм Форда–Фалкерсона)
• Теорема Биркгофа – Фон Неймана (1946 г.)
• Теорема Дилворта .

В частности, ^{[8] [9]} имеются простые доказательства импликаций теоремы Дилворта ⇔ теоремы Холла ⇔ теоремы Кёнига–Эгервари ⇔ теоремы Кёнига.

Бесконечные семьи

Вариант Маршалла Холла-младшего

Тщательно изучив оригинальное доказательство Филипа Холла , Маршалл Холл-младший (не родственник Филиппа Холла) смог подправить результат таким образом, что это позволило доказательству работать для бесконечного . ^[10] Этот вариант расширяет теорему Филипа Холла о браке. ${\displaystyle {\mathcal {F}}}$

Предположим, что , является (возможно, бесконечным) семейством конечных множеств, которые не обязательно должны быть различны, тогда имеет трансверсаль тогда и только тогда, когда удовлетворяет условию брака. ${\displaystyle {\mathcal {F}}=\{A_{i}\}_{i\in I}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

Условие брака не распространяется

Следующий пример, принадлежащий Маршаллу Холлу-младшему, показывает, что условие брака не гарантирует существования трансверсали в бесконечном семействе, в котором допускаются бесконечные множества.

Пусть будет семейством, , для . Условие брака выполняется для этого бесконечного семейства, но трансверсаль построить нельзя. ^[11] ${\displaystyle {\mathcal {F}}}$ ${\displaystyle A_{0}=\mathbb {N} }$ ${\displaystyle A_{i}=\{i-1\}}$ ${\displaystyle i\geq 1}$

Теоретико-графовая формулировка варианта Маршалла Холла

Теоретико-графовая формулировка расширения Маршалла Холла теоремы о браке может быть сформулирована следующим образом: для данного двудольного графа со сторонами A и B мы говорим, что подмножество C из B меньше или равно по размеру подмножеству D из A в графе , если в графе существует инъекция (а именно, с использованием только ребер графа) из C в D , и что оно строго меньше в графе, если, кроме того, в графе нет инъекции в другом направлении. Обратите внимание, что исключение в графе приводит к обычному понятию сравнения мощностей. Теорема о бесконечном браке утверждает, что существует инъекция из A в B в графе, тогда и только тогда, когда нет подмножества C из A такого, что N ( C ) строго меньше C в графе. ^[12]

Более общая задача выбора (не обязательно отдельного) элемента из каждого набора непустых множеств (без ограничений на количество множеств или размер множеств) в общем случае разрешается только в том случае, если принята аксиома выбора .

Вариант дробного соответствия

Дробное паросочетание в графе — это присвоение неотрицательных весов каждому ребру таким образом, что сумма весов, смежных с каждой вершиной, не превышает 1. Дробное паросочетание является X -совершенным, если сумма весов, смежных с каждой вершиной, равна точно 1. Следующие условия эквивалентны для двудольного графа G = ( X+Y, E ): ^[13]

• G допускает X-совершенное паросочетание.
• G допускает X-совершенное дробное паросочетание. Импликация следует непосредственно из того факта, что X -совершенное паросочетание является частным случаем X -совершенного дробного паросочетания, в котором каждый вес равен либо 1 (если ребро входит в паросочетание), либо 0 (если нет).
• G удовлетворяет условию брака Холла. Импликация верна, поскольку для каждого подмножества W из X сумма весов вблизи вершин W равна | W |, поэтому смежные с ними ребра обязательно смежны по крайней мере с |W| вершинами Y .

Количественный вариант

Когда условие Холла не выполняется, исходная теорема говорит нам только о том, что идеального паросочетания не существует, но не говорит, какое наибольшее паросочетание существует. Чтобы узнать эту информацию, нам нужно понятие дефицита графа . Если дан двудольный граф G = ( X + Y , E ), дефицит G относительно X равен максимуму, по всем подмножествам W из X , разности | W | - | N _G ( W )|. Чем больше дефицит, тем дальше граф от удовлетворения условия Холла.

Используя теорему Холла о браке, можно доказать, что если дефект двудольного графа G равен d , то G допускает паросочетание размера не менее | X |- d .

Обобщения

• Характеристика совершенных паросочетаний в общих графах (которые не обязательно являются двудольными) дается теоремой Тутте .
• Обобщение теоремы Холла на двудольные гиперграфы обеспечивается различными теоремами типа Холла для гиперграфов .

Примечания

1. Холл 1986, стр. 51. Альтернативная форма теоремы о браке применима к конечным семействам множеств, которые могут быть бесконечными. Однако ситуация, когда имеется бесконечное число множеств, допуская при этом бесконечные множества, не допускается.
2. Райхмейдер 1984, стр.90
3. Хакселл, П. (2011). «О формировании комитетов». The American Mathematical Monthly . 118 (9): 777–788. doi :10.4169/amer.math.monthly.118.09.777. ISSN  0002-9890. JSTOR  10.4169/amer.math.monthly.118.09.777. S2CID  27202372.
4. ДеВос, Мэтт. "Теория графов" (PDF) . Университет Саймона Фрейзера .
5. Button, Jack; Chiodo, Maurice; Zeron-Medina Laris, Mariano (2014). "Coset Intersection Graphs for Groups". The American Mathematical Monthly . 121 (10): 922–26. arXiv : 1304.6111 . doi :10.4169/amer.math.monthly.121.10.922. S2CID  16417209. Для подгруппы с конечным индексом существование лево-правой трансверсали хорошо известно, иногда представляемое как приложение теоремы Холла о браке. ${\displaystyle H}$ ${\displaystyle G}$
6. Холл, Маршалл (1945). «Теорема существования для латинских квадратов». Bull. Amer. Math. Soc . 51 (6): 387–388. doi : 10.1090/S0002-9904-1945-08361-X .
7. Название этой теоремы в литературе непоследовательно. Существует результат, касающийся паросочетаний в двудольных графах и его интерпретация как покрытия (0,1)-матриц. Холл (1986) и ван Линт и Уилсон (1992) называют матричную форму теоремой Кёнига, в то время как Робертс и Тесман (2009) называют эту версию теоремой Кёнига-Эгервари. Версия для двудольного графа называется теоремой Кёнига Кэмероном (1994) и Робертсом и Тесманом (2009).
8. Эквивалентность семи основных теорем комбинаторики
9. Райхмейдер 1984
10. Холл 1986, стр. 51
11. Холл 1986, стр. 51
12. Ахарони, Рон (февраль 1984 г.). «Теорема двойственности Кёнига для бесконечных двудольных графов». Журнал Лондонского математического общества . s2-29 (1): 1–12. doi :10.1112/jlms/s2-29.1.1. ISSN  0024-6107.
13. "co.combinatorics - версия теоремы Холла о браке с дробным соответствием". MathOverflow . Получено 29-06-2020 .

Ссылки

• Бруальди, Ричард А. (2010), Вводная комбинаторика , Аппер Сэддл Ривер, Нью-Джерси: Prentice-Hall/Pearson, ISBN 978-0-13-602040-0
• Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы , Кембридж: Cambridge University Press, ISBN 978-0-521-45761-3
• Холл, Маршалл-младший (1986), Комбинаторная теория (2-е изд.), Нью-Йорк: John Wiley & Sons, ISBN 978-0-471-09138-7
• Холл, Филип (1935), «О представителях подмножеств», J. London Math. Soc. , 10 (1): 26–30, doi :10.1112/jlms/s1-10.37.26
• Халмос, Пол Р.; Воган, Герберт Э. (1950), «Проблема брака», American Journal of Mathematics , 72 (1): 214–215, doi :10.2307/2372148, JSTOR  2372148, MR  0033330
• Райхмейдер, ПФ (1984), Эквивалентность некоторых комбинаторных теорем о сопоставлении , Polygonal Publishing House, ISBN 978-0-936428-09-3
• Робертс, Фред С.; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), Бока-Ратон: CRC Press, ISBN 978-1-4200-9982-9
• ван Линт, Дж. Х.; Уилсон, Р. М. (1992), Курс комбинаторики , Кембридж: Cambridge University Press, ISBN 978-0-521-42260-4

Внешние ссылки

• Теорема о браке в разрубании узла
• Теорема о браке и алгоритм в cut-the-knot
• Теорема Холла о браке интуитивно объяснена в записях Лаки.

В данной статье использованы материалы из доказательства теоремы Холла о браке на PlanetMath , лицензированные по лицензии Creative Commons Attribution/Share-Alike License .