Теорема Холла о сочетаниях и графах

Введение

Результат в комбинаторике и теории графов
В математике теорема Холла о браке, доказанная , является теоремой с двумя эквивалентными формулировками. В каждом случае теорема дает необходимое и достаточное условие для существования объекта: комбинаторная формулировка отвечает на вопрос, имеет ли конечная коллекция множеств поперечное сечение — то есть, можно ли выбрать элемент из каждого множества без повторений. Условие Холла состоит в том, что для любой группы множеств из этой коллекции общее число различных элементов, которые они содержат, должно быть не меньше, чем число множеств в группе. Графовая формулировка отвечает на вопрос, имеет ли конечный двудольный граф совершенное паросочетание — то есть, способ однозначно сопоставить каждую вершину из одной доли с соседней вершиной из другой доли. Условие Холла состоит в том, что любое подмножество вершин из одной доли имеет окрестность равного или большего размера.

Заявление

Пусть – конечное семейство множеств (отметьте, что хотя само не может быть бесконечным, множества в нем могут быть бесконечными, и может содержать одно и то же множество несколько раз). Пусть – объединение всех множеств из , множество элементов, принадлежащих хотя бы одному из этих множеств. Трансверсалью для является подмножество , которое можно получить, выбирая различные элементы из каждого множества из . Это понятие можно формализовать, определив трансверсаль как образ инъективной функции , такой что для каждого . Альтернативным термином для трансверсали является система различных представителей. Семейство удовлетворяет условию сочетаемости, когда каждое подсемейство содержит не менее различных элементов, чем количество множеств в нем. То есть, для всех ,

Если трансверсаль существует, то условие сочетаемости должно выполняться: функция, используемая для определения трансверсали, отображает в подмножество его объединения размером , следовательно, само объединение должно быть не меньше по размеру. Теорема Холла утверждает, что обратное также верно:

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

Пусть G — конечный двудольный граф с двудольными множествами A и B и множеством ребер E. Идеальное (или насыщающее) совпадение — это совпадение, то есть множество непересекающихся ребер, которое покрывает все вершины в A. Для подмножества S множества A обозначим через N(S) окрестность S в B, то есть множество всех вершин в B, смежных хотя бы с одним элементом из S. Теорема о замужестве в этой формулировке утверждает, что идеальное совпадение существует тогда и только тогда, когда для каждого подмножества S множества A выполняется условие |N(S)| ≥ |S|. Иными словами, каждое подмножество A должно иметь достаточное количество соседей в B.

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

В полном соответствии, каждое ребро, инцидентное вершине , соединяется с различным соседом вершины в графе , таким образом, число этих соединенных соседей не меньше . Число всех соседей вершины не меньше этого числа.

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

Рассмотрим противопоставленное утверждение: если не существует совершенного паросочетания, то условие Холла должно быть нарушено хотя бы для одного множества. Пусть M — максимальное паросочетание, и пусть v — произвольная несытая вершина из V. Рассмотрим все чередующиеся пути (пути в V, в которых поочередно используются рёбра, не входящие и входящие в M), начинающиеся из v. Пусть A — множество вершин в этих путях, принадлежащих M (включая саму v), а B — множество вершин в этих путях, не принадлежащих M. Тогда каждая вершина из A соединена в M с вершиной из B, поскольку чередующийся путь к несытой вершине можно использовать для увеличения размера паросочетания, меняя принадлежность каждого ребра этого пути к M или не к M. Следовательно, размер A не меньше числа соединённых с A вершин из B, плюс один для несытой вершины v. То есть, |A| ≥ |B| + 1. Однако для каждой вершины a из A, каждый её сосед принадлежит A: чередующийся путь к a можно найти либо удалив ребро паросочетания из чередующегося пути к v, либо добавив несытое ребро к чередующемуся пути к v. Таким образом, A = B ∪ {v}, и |A| > |B|, что показывает, что условие Холла нарушено.

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

Проблема в комбинаторной формулировке, заданная конечной семьей конечных множеств с объединением, может быть представлена в виде двудольного графа, где каждое ребро соединяет множество из с элементом этого множества. Полное соответствие в этом графе определяет систему однозначных представителей для . В обратном направлении, из любого двудольного графа можно определить конечное семейство множеств – семейство окрестностей вершин в – такое, что любая система однозначных представителей для этого семейства соответствует полному соответствию в . Таким образом, комбинаторная формулировка для конечных семейств конечных множеств и графовая формулировка для конечных графов эквивалентны. Та же эквивалентность распространяется на бесконечные семейства конечных множеств и на некоторые бесконечные графы. В этом случае условие конечности каждого множества соответствует условию, что в двудольном графе , каждая вершина в должна иметь конечную степень. Степени вершин в не ограничены.

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

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

Приложения

Теорема имеет множество применений. Например, для стандартной колоды карт, разданной в 13 стопок по 4 карты в каждой, теорема о браке подразумевает, что можно выбрать по одной карте из каждой стопки так, чтобы выбранные карты содержали ровно одну карту каждой масти (туз, 2, 3, …, дама, король). Это можно сделать, построив двудольный граф, одна доля которого содержит 13 стопок, а другая – 13 мастей. Дальнейшее доказательство следует из условия о браке. В более общем случае, любой регулярный двудольный граф имеет совершенное паросочетание. В более абстрактном плане, пусть G – группа, а H – подгруппа конечного индекса в G. Тогда теорема о браке может быть использована для доказательства существования множества S, являющегося поперечным сечением как для множества левых смежных классов, так и для множества правых смежных классов H в G. Теорема о браке используется в стандартных доказательствах того факта, что латинский прямоугольник размера m × n всегда можно расширить до латинского прямоугольника размера m × (n+1) при n < m, и, следовательно, до латинского квадрата.

Маршалл Холл-младший вариант

Внимательно изучив первоначальное доказательство Филиппа Холла, Маршалл Холл-младший (не состоящий с Филиппом Холлом в родстве) смог незначительно изменить результат, что позволило применить доказательство к бесконечным множествам. Этот вариант является обобщением теоремы о браке Филиппа Холла. Пусть , — (возможно, бесконечное) семейство конечных множеств, которые не обязаны быть различными, тогда у существует поперечное сечение, если и только если удовлетворяет условию брака.

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

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

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

Теоретическая формулировка расширения теоремы о браке Маршала Холла может быть сформулирована следующим образом: Для двудольного графа со сторонами A и B, подмножество C из B считается меньше или равным по размеру подмножеству D из A в графе, если существует инъекция в графе (то есть, используя только ребра графа) из C в D, и строго меньше в графе, если дополнительно не существует инъекции в графе из D в C. Следует отметить, что исключение рассмотрения графа приводит к обычному понятию сравнения мощностей множеств. Бесконечная теорема о браке утверждает, что инъекция из 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 разности |W| − |NG(W)|. Чем больше дефицит, тем дальше граф от выполнения условия Холла. Используя теорему Холла о браке, можно доказать, что если дефицит двудольного графа G равен d, то G содержит паросочетание размера не менее |X| − d.

Обобщения

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