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

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

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

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

Заявление

Позволять ${\mathcal {F}}$ — конечное семейство множеств (заметим, что хотя ${\mathcal {F}}$ не может быть бесконечным, множества в нем могут быть такими, и ${\mathcal {F}}$ может содержать один и тот же набор несколько раз ). Позволять $X$ быть объединением всех множеств в ${\mathcal {F}}$, набор элементов, принадлежащих хотя бы одному из его наборов. Трансверсаль ​ для ${\mathcal {F}}$ является подмножеством $X$ которые можно получить, выбрав отдельный элемент из каждого множества в ${\mathcal {F}}$. Эту концепцию можно формализовать, определив трансверсаль как образ инъективной функции. $f:{\mathcal {F}}\to X$ такой, что $f(S)\in S$ для каждого $S\in {\mathcal {F}}$. Альтернативный термин для трансверсальности — система отдельных представителей .

Коллекция ${\mathcal {F}}$ удовлетворяет условию брака , когда каждое подсемейство ${\mathcal {F}}$ содержит по крайней мере столько же различных членов, сколько его множеств. То есть для всех ${\mathcal {G}}\subseteq {\mathcal {F}}$, $$|{\mathcal {G}}|\leq {\Bigl |}\bigcup _{S\in {\mathcal {G}}}S{\Bigr |}.$$ Если трансверсаль существует, то условие брака должно быть истинным: функция $f$ используется для определения трансверсальных карт ${\mathcal {G}}$ к подмножеству его объединения размером, равным $|{\mathcal {G}}|$, поэтому весь союз должен быть как минимум такого же размера. Теорема Холла утверждает, что верно и обратное:

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

Примеры

пример 1, условие брака соблюдено

Пример 1

Рассмотрим семью ${\mathcal {F}}=\{A_{1},A_{2},A_{3}\}$ с $X=\{1,2,3,4,5\}$ и $${\begin{aligned}A_{1}&=\{1,2,3\}\\A_{2}&=\{1,4,5\}\\A_{3}&=\{3,5\}.\\\end{aligned}}$$ Поперечное $\{1,3,5\}$ может быть сгенерировано функцией, которая отображает $A_{1}$ к $1$, $A_{2}$ к $5$, и $A_{3}$ к $3$или, альтернативно, с помощью функции, которая отображает $A_{1}$ к $3$, $A_{2}$ к $1$, и $A_{3}$ к $5$. Существуют и другие трансверсали, например $\{1,2,3\}$ и $\{1,4,5\}$. Поскольку в этой семье есть хотя бы одна трансверсаль, условие брака выполнено. Каждое подсемейство ${\mathcal {F}}$ имеет размер, равный множеству представителей, с которыми он сопоставлен, что меньше или равно размеру объединения подсемейства.

пример 2, нарушено условие брака

Пример 2

Учитывать ${\mathcal {F}}=\{A_{1},A_{2},A_{3},A_{4}\}$ с $${\begin{aligned}A_{1}&=\{2,3,4,5\}\\A_{2}&=\{4,5\}\\A_{3}&=\{5\}\\A_{4}&=\{4\}.\\\end{aligned}}$$ Никакой допустимой трансверсали не существует; условие брака нарушено, о чем свидетельствует подсемейство ${\mathcal {G}}=\{A_{2},A_{3},A_{4}\}$. Здесь число множеств в подсемействе равно $|{\mathcal {G}}|=3$, а объединение трех множеств $A_{2}\cup A_{3}\cup A_{4}=\{4,5\}$ содержит всего два элемента.

Нижняя оценка различного числа трансверсалей, которые может иметь данное конечное семейство ${\mathcal {F}}$ размера $n$ может иметь, получается следующим образом: если каждое из множеств в ${\mathcal {F}}$ имеет мощность $\geq r$, то количество различных трансверсалей для ${\mathcal {F}}$ либо $r!$ если $r\leq n$, или $r(r-1)\cdots (r-n+1)$ если $r>n$.

Напомним, что трансверсаль для семьи ${\mathcal {F}}$ является упорядоченной последовательностью, поэтому две разные трансверсали могут содержать одинаковые элементы. Например, коллекция $A_{1}=\{1,2,3\}$, $A_{2}=\{1,2,5\}$ имеет $(1,2)$ и $(2,1)$ отдельные поперечные тузы.

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

синие края представляют собой совпадение

Позволять $G=(X,Y,E)$ — конечный двудольный граф с двудольными множествами $X$ и $Y$ и набор кромок $E$. Ан $X$- идеальное соответствие (также называемое $X$-насыщающее паросочетание ) — паросочетание , набор непересекающихся ребер, покрывающий каждую вершину в $X$.

Для подмножества $W$ из $X$, позволять $N_{G}(W)$ обозначим окрестность ​ $W$ в $G$, множество всех вершин в $Y$ которые примыкают хотя бы к одному элементу $W$. Теорема о браке в этой формулировке утверждает, что существует $X$-совершенное совпадение тогда и только тогда, когда для каждого подмножества $W$ из $X$: $$|W|\leq |N_{G}(W)|.$$ Другими словами, каждое подмножество $W$ из $X$ должно иметь достаточно много соседей в $Y$.

Доказательство

Необходимость

В $X$- идеальное соответствие $M$, каждое ребро, инцидентное $W$ соединяется с отдельным соседом $W$ в $Y$, поэтому количество этих совпадающих соседей не менее $|W|$. Число всех соседей $W$ по крайней мере столь же велик.

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

Рассмотрим противоположное : если нет $X$-совпадение идеальное, то условие Холла должно быть нарушено хотя бы для одного $W\subseteq X$. Позволять $M$ будет максимальным паросочетанием, и пусть $u$ быть любой несовпадающей вершиной в $X$. Рассмотрим все альтернативные пути (пути в $G$ которые поочередно используют края снаружи и внутри $M$), начиная с $u$. Позволять $W$ — множество вершин этих путей, принадлежащих $X$ (включая $u$ себя) и пусть $Z$ — множество вершин этих путей, принадлежащих $Y$. Тогда каждая вершина в $Z$ соответствует $M$ в вершину в $W$, поскольку альтернативный путь к несовпадающей вершине может использоваться для увеличения размера сопоставления путем переключения того, принадлежит ли каждое из его ребер $M$ или нет. Следовательно, размер $W$ это как минимум число $|Z|$ из этих подходящих соседей $Z$, плюс один за несовпадающую вершину $u$. То есть, $|W|\geq |Z|+1$. Однако для каждой вершины $v\in W$, каждый сосед $w$ из $v$ принадлежит $Z$: альтернативный путь к $w$ можно найти либо удалив совпадающее ребро $vw$ с альтернативного пути на $v$или добавив несовпадающее ребро $vw$ на альтернативный путь к $v$. Поэтому, $Z=N_{G}(W)$ и $|W|\geq |N_{G}(W)|+1$, показывая, что условие Холла нарушено.

Эквивалентность комбинаторной формулировки и формулировки теории графов

Задача в комбинаторной постановке, определяемая конечным семейством конечных множеств. ${\mathcal {F}}$ с профсоюзом $X$ можно перевести в двудольный граф $G=({\mathcal {F}},X,E)$ где каждое ребро соединяет множество в ${\mathcal {F}}$ к элементу этого множества. Ан ${\mathcal {F}}$-совершенное паросочетание в этом графе определяет систему уникальных представителей для ${\mathcal {F}}$. В обратном направлении из любого двудольного графа $G=(X,Y,E)$ можно определить конечное семейство множеств — семейство окрестностей вершин в $X$, такая что любая система уникальных представителей этого семейства соответствует $X$- идеальное соответствие $G$. Таким образом, комбинаторная формулировка для конечных семейств конечных множеств и теоретико-графовая формулировка для конечных графов эквивалентны.

Та же эквивалентность распространяется на бесконечные семейства конечных множеств и на некоторые бесконечные графы. В этом случае условие конечности каждого множества соответствует условию, что в двудольном графе $G=(X,Y,E)$, каждая вершина в $X$ должна иметь конечную степень . Степени вершин в $Y$ не ограничены.

Топологическое доказательство

Теорему Холла можно доказать (неконструктивно) на основе леммы Спернера .

Приложения

Теорема имеет множество приложений. Например, для стандартной колоды карт , разложенной на 13 стопок по 4 карты в каждой, теорема брака предполагает, что из каждой стопки можно выбрать по одной карте так, чтобы в выбранных картах было ровно по одной карте каждого достоинства (Туз, 2 , 3, ..., Ферзь, Король). Это можно сделать, построив двудольный граф, в одном разделе которого содержится 13 стопок, а в другом — 13 рангов. Остальные доказательства следуют из условия брака. В более общем смысле любой регулярный двудольный граф имеет идеальное паросочетание.

Более абстрактно, пусть $G$ быть группой , и $H$ конечного индекса — подгруппа группы $G$. Тогда теорему о браке можно использовать, чтобы показать, что существует множество $T$ такой, что $T$ является трансверсалью как для набора левых классов , так и для правых смежных $H$ в $G$.

Теорема о браке используется в обычных доказательствах того факта, что $r\times n$ Латинский прямоугольник всегда можно расширить до $(r+1)\times n$ Латинский прямоугольник, когда $r<n$, и так, в конечном итоге, к латинскому квадрату .

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

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

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

В частности, существуют простые доказательства следствий: теорема Дилворта ⇔ теорема Холла ⇔ теорема Кенига–Эгервари ⇔ теорема Кенига.

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

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

Внимательно изучив Филипа Холла оригинальное доказательство , Маршалл Холл-младший (не имеющий отношения к Филипу Холлу) смог изменить результат таким образом, чтобы доказательство работало бесконечно долго. ${\mathcal {F}}$. Этот вариант расширяет теорему Филипа Холла о браке.

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Дефицит (теория графов)

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

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

Обобщения

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

Ссылки

• Бруальди, Ричард А. (2010), Вводная комбинаторика , Аппер-Сэддл-Ривер, Нью-Джерси: Прентис-Холл / Пирсон, ISBN  978-0-13-602040-0
• Кэмерон, Питер Дж. (1994), Комбинаторика: темы, методы, алгоритмы , Кембридж: Издательство Кембриджского университета, ISBN  978-0-521-45761-3
• Холл, Маршалл младший (1986), Комбинаторная теория (2-е изд.), Нью-Йорк: John Wiley & Sons, ISBN  978-0-471-09138-7
• Холл, Филип (1935), «О представителях подмножеств», J. London Math. Соц. , 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, ISBN  978-0-936428-09-3
• Робертс, Фред С.; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), Бока-Ратон: CRC Press, ISBN  978-1-4200-9982-9
• ван Линт, Дж. Х.; Уилсон, Р.М. (1992), Курс комбинаторики , Кембридж: Издательство Кембриджского университета, ISBN  978-0-521-42260-4

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

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

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