Теоремы холловского типа для гиперграфов

В комбинаторике , теоремы Холла-типа для гиперграфов несколько обобщения теоремы брачном Холла из графиков в гиперграфы . Такие теоремы были доказаны Офра Kessler, ^{[1] [2]} Рон Ахарони , ^{[3] [4]} Пенни Haxell , ^{[5] [6]} Рой Мешулама , ^[7] и другие.

Предварительные мероприятия [ править ]

Брак Холла теорема дает условие , гарантирующее , что двудольный граф ( X + Y, E ) допускает полное совпадение , или - в более общем плане - паросочетание, насыщающего все вершины Y . Условие включает в число соседей подмножеств Y . Обобщение теоремы Холла на гиперграфы требует обобщения понятий двудольности, идеального соответствия и соседей.

1. Двудольный : понятие двудольного может быть распространено на гиперграфы многими способами (см. Двудольный гиперграф ). Здесь мы определяем гиперграф как двудольный, если он точно 2-раскрашиваем , т. Е. Его вершины могут быть 2-раскрашены так, что каждое гиперребро содержит ровно одну желтую вершину. Другими словами, V можно разбить на два множества X и Y , так что каждый гиперребро содержит ровно одну вершину Y . ^[1] двудольный граф является частным случаем , в котором каждое ребро содержит ровно одну вершину Y , а также ровно одну вершину X; в двудольного гиперграфе, каждый гиперребро содержит ровно одну вершину Y , но может содержать ноль или более вершин X . Например, гиперграф ( V , E ) с V = {1,2,3,4,5,6} и E = {{1,2,3}, {1,2,4}, {1,3 , 4}, {5,2}, {5,3,4,6}} двудольные с Y = {1,5} и X = {2,3,4,6}.

2. Совершенное паросочетание : паросочетание в гиперграфе H = (V, E) - это подмножество F в E , такое, что любые два гиперребра F не пересекаются. Если H является двудольным с частями X и Y , то размер каждого сопоставления, очевидно, не превосходит | Y |, Соответствие называется Y-идеальным (или Y-насыщающим ), если его размер точно | Y |, Другими словами: каждая вершина Y появляется ровно один гиперребро из М . Это определение сводится к стандартному определению Y-совершенное паросочетание в двудольном графе.

3. Соседи : дан двудольный гиперграф H = ( X + Y, E ) и подмножество Y ₀ в Y, соседи Y ₀ - это подмножества X, которые имеют общие гиперребра с вершинами Y ₀ . Формально: . Например, в гиперграфе из пункта 1 имеем: N _H ({1}) = {{2,3}, {2,4}, {3,4}} и N _H ({5}) = { {2}, {3,4,6}} и N _H ({1,5}) = {{2,3}, {2,4}, {3,4}, {2}, {3,4 , 6}}. Обратите внимание, что в двудольном графе каждый сосед является одноэлементным - соседи - это просто вершины X, которые примыкают к одной или нескольким вершинам Y${\ Displaystyle N_ {H} (Y_ {0}): = \ {X_ {0} \ substeq X ~~ | ~~ \ exists y_ {0} \ in Y_ {0}: ~ \ {y_ {0} \ } \ чашка X_ {0} \ in E \}}$₀ . В двудольном гиперграфе каждый сосед - это множество - соседи - это подмножества X , которые «смежны» с одной или несколькими вершинами Y ₀ .

Поскольку N _H ( Y ₀ ) содержит только подмножества X , можно определить гиперграф, в котором множество вершин равно X, а множество ребер - N _H ( Y ₀ ). Мы называем это соседство-гиперграфом Y ₀ и обозначим его: . Обратите внимание, что если H - простой двудольный граф, соседний гиперграф каждого Y ₀ содержит только соседей Y ₀ в X , каждый из которых имеет петлю.${\ displaystyle H_ {H} (Y_ {0}): = (X, N_ {H} (Y_ {0}))}$

Недостаточность состояния Холла [ править ]

Условие Холла требует, чтобы для каждого подмножества Y ₀ из Y множество соседей Y _{0 было} достаточно большим. Для гиперграфов этого условия недостаточно. Например, рассмотрим трехчастный гиперграф с ребрами:

{{1, a, A}, {2, a, B}}

Пусть Y = {1,2}. Каждая вершина в Y имеет соседа, а сама Y имеет двух соседей: N _H ( Y ) = {{a, A}, {a, B}}. Но нет никакого Y- идеального совпадения, поскольку оба края перекрываются. Можно попытаться исправить это, потребовав, чтобы N _H ( Y ₀ ) содержало по крайней мере | Y ₀ | непересекающиеся ребра, а не просто | Y ₀ | края. Другими словами: H _H ( Y ₀ ) должен содержать соответствие размера не менее | Y ₀|, Наибольший размер сопоставления в гиперграфе H называется его числом сопоставления и обозначается (таким образом, H допускает Y -совершенное сопоставление тогда и только тогда ). Однако этого исправления недостаточно, как показывает следующий трехсторонний гиперграф:${\ displaystyle \ nu (H)}$${\ Displaystyle \ Nu (H) = | Y |}$

{{1, a, A}, {1, b, B}, {2, a, B}, {2, b, A}}

Пусть Y = {1,2}. Снова каждая вершина в Y имеет соседа, а сама Y имеет четырех соседей: N _H ( Y ) = {{a, A}, {a, B}, {b, A}, {b, B}}. Более того, поскольку H _H ( Y ) допускает соответствие размера 2, например {{a, A}, {b, B}} или {{a, B}, {b, A}}. Однако H не допускает Y -совершенного паросочетания, поскольку каждое гиперребро, содержащее 1, перекрывает каждое гиперребро, содержащее 2.${\ displaystyle \ nu (H_ {H} (Y)) = 2}$

Таким образом, чтобы гарантировать идеальное совпадение, необходимо более строгое условие. Предлагались различные такие условия.

Условия Ахарони: максимальное соответствие [ править ]

Пусть H = ( X + Y , E ) - двудольный гиперграф (как определено в п. 1. выше), в котором размер каждого гиперребра равен в точности r для некоторого целого числа r > 1. Предположим, что для любого подмножества Y ₀ из Y имеет место неравенство

${\ displaystyle \ nu (N_ {H} (Y_ {0})) \ geq (r-1) \ cdot (| Y_ {0} | -1) +1}$

На словах: соседний гиперграф Y ₀ допускает паросочетание больше, чем ( r - 1) ( | Y ₀ | - 1). Тогда H допускает Y -совершенное паросочетание (как определено в п. 2. выше).

Об этом впервые предположил Ахарони. ^[3] Это было доказано с Офрой Кесслер для двудольных гиперграфов, в которых | Y | ≤ 4 ^[1] и для | Y | = 5. ^[2] Позже это было доказано для всех r- однородных гиперграфов. ^{[6] : Следствие 1.2.}

В простых графиках [ править ]

Для двудольного простого графа r = 2, и условие Ахарони становится . Более того, соседний гиперграф (как определено в п. 3. выше) содержит только синглтоны - синглтоны для каждого соседа Y ₀ . Поскольку синглтоны не пересекаются, весь набор синглтонов совпадает. Следовательно, количество соседей Y ₀ . Таким образом, условие Ахарони становится для каждого подмножества Y ₀ из Y :${\displaystyle \nu (H_{H}(Y_{0}))\geq |Y_{0}|}$${\displaystyle \nu (H_{H}(Y_{0}))=|N_{H}(Y_{0})|=}$

${\displaystyle |N_{H}(Y_{0})|\geq |Y_{0}|}$.

Это как раз и есть условие брака Холла.

Герметичность [ править ]

Следующий пример показывает, что коэффициент ( r - 1) не может быть улучшен. Выберите какое-нибудь целое число m > 1. Пусть H = ( X + Y, E ) - следующий r -равномерный двудольный гиперграф:

• Y = {1, ..., m };
• E - объединение E ₁ , ..., E _m (где E _i - множество гиперребер, содержащих вершину i ), и:
  • Для каждого i из {1, ..., m -1}, E _i содержит r -1 непересекающихся гиперребер размера r , { i , x _{i , 1,1} , ..., x _{i, 1, r −1} }, ...,, { i , x _{i , r-1,1} , ..., x _{i, r-1, r −1} }.
  • E _m содержит m -1 гиперребер размера r , { m , x _1,1,1 , ..., x _{1, r -1 , r -1} }, ... ,, { m , x _{m -1, 1,1} , ..., x _{m -1, r -1,1} }. Обратите внимание, что ребро i в E _m пересекает все ребра в E _i .

Эта H не допускает Y -совершенного паросочетания, поскольку каждое гиперребро, содержащее m, пересекает все гиперребра в E _i для некоторого i < m .

Однако каждое подмножество Y ₀ из Y удовлетворяет следующему неравенству:

${\displaystyle \nu (H_{H}(Y_{0}))\geq (r-1)\cdot (|Y_{0}|-1)}$

Поскольку содержит по крайней мере гиперребра, и все они не пересекаются.${\displaystyle H_{H}(Y_{0}\setminus \{m\})}$${\displaystyle (r-1)\cdot (|Y_{0}|-1)}$

Дробное сопоставление [ править ]

Наибольший размер дробного согласования в H обозначается как . Ясно . Предположим, что для любого подмножества Y ₀ из Y выполняется более слабое неравенство:${\displaystyle \nu ^{*}(H)}$${\displaystyle \nu ^{*}(H)\geq \nu (H)}$

${\displaystyle \nu ^{*}(H_{H}(Y_{0}))\geq (r-1)\cdot (|Y_{0}|-1)+1}$

Было высказано предположение, что и в этом случае H допускает Y -совершенное паросочетание. Эта более сильная гипотеза была доказана для двудольных гиперграфов, в которых | Y | = 2. ^[4]

Позже было доказано ^[4], что если это условие выполнено, то H допускает Y -совершенное дробное паросочетание, т . Е .. Это слабее, чем совпадение по Y , которое эквивалентно .${\displaystyle \nu ^{*}(H)=|Y|}$${\displaystyle \nu (H)=|Y|}$

Состояние Хакселла: наименьшее поперечное [ править ]

Трансверсально (также называется вершиной переплета или ударять-набор ) в гиперграфа H = ( V , E ) представляет собой подмножество U в V такой , что каждая гиперребро в Е содержит , по меньшей мере , одну вершину U . Наименьший размер трансверсали в H обозначается через .${\displaystyle \tau (H)}$

Пусть H = ( X + Y , E ) двудольный гиперграф, в котором размер каждого гиперребра не превосходит r для некоторого целого r > 1. Предположим, что для любого подмножества Y ₀ в Y выполняется следующее неравенство:

${\displaystyle \tau (H_{H}(Y_{0}))\geq (2r-3)\cdot (|Y_{0}|-1)+1}$

На словах: соседний гиперграф Y ₀ не имеет трансверсали размера (2 r - 3) ( Y ₀ - 1) или меньше.

Тогда H допускает Y -совершенное паросочетание (как определено в п. 2. выше). ^{[5] : Теорема 3.}

В простых графиках [ править ]

Для двудольного простого графа r = 2, поэтому 2 r -3 = 1, и условие Хакселла становится . Более того, соседний гиперграф (как определено в п. 3. выше) содержит только синглтоны - синглтоны для каждого соседа Y ₀ . В гиперграфе синглетонов трансверсаль должна содержать все вершины. Следовательно, количество соседей Y ₀ . Таким образом, условие Хакселла становится для каждого подмножества Y ₀ из Y :${\displaystyle \tau (H_{H}(Y_{0}))\geq |Y_{0}|}$${\displaystyle \tau (H_{H}(Y_{0}))=|N_{H}(Y_{0})|=}$

${\displaystyle |N_{H}(Y_{0})|\geq |Y_{0}|}$.

Это как раз и есть условие брака Холла. Таким образом, из теоремы Хакселла следует теорема Холла о браке для двудольных простых графов.

Герметичность [ править ]

Следующий пример показывает, что коэффициент (2 r - 3) не может быть улучшен. Пусть H = ( X + Y, E ) - r -равномерный двудольный гиперграф с:

• Y = {0,1}
• X = { x _ij  : 1 ≤ i , j ≤ r -1} [так | X | = ( г -1) ² ].
• E = E ₀ u E ₁ , где
  • E ₀ = {{0, x _{i 1} , ..., x _{i ( r -1)} } | 1 ≤ i ≤ r -1} [так что E ₀ содержит r -1 гиперребер].
  • E ₁ = {{1, x _{1j [1]} , ..., x _{( r -1) j [r-1]} } | 1 ≤ j [ k ] ≤ r -1 для 1 ≤ k ≤ r -1}. [так что E ₁ содержит ( r -1) ^{r -1} гиперребер].

Эта H не допускает Y -совершенного паросочетания, поскольку каждое гиперребро, содержащее 0, пересекает каждое гиперребро, содержащее 1.

Однако каждое подмножество Y ₀ из Y удовлетворяет следующему неравенству:

${\displaystyle \tau (H_{H}(Y_{0}))\geq (2r-3)\cdot (|Y_{0}|-1)}$

он лишь немного слабее (на 1), чем требуется по теореме Хакселла. Чтобы убедиться в этом, достаточно проверить подмножество Y ₀ = Y , так как это единственное подмножество, правая часть которого больше 0. Окрестный гиперграф Y равен ( X , E ₀₀ u E ₁₁ ) куда:

• E ₀₀ = {{ x _{i 1} , ..., x _{i ( r -1)} } | 1 ≤ i ≤ r -1}.
• E ₁₁ = {{ x _{1j [1]} , ..., x _{( r -1) j [r-1]} } | 1 ≤ j [ k ] ≤ r -1 для 1 ≤ k ≤ r -1}

Можно визуализировать вершины X, расположенные на сетке ( r -1) раз (r-1). Гиперребра E ₀₀ - это r -1 ряды. Гиперребра E ₁₁ - это ( r -1) ^{r -1} выборки одного элемента в каждой строке и каждом столбце. Чтобы покрыть гиперребра E _10, нам понадобится r - 1 вершина - по одной вершине в каждой строке. Поскольку все столбцы в конструкции симметричны, мы можем предположить, что мы берем все вершины в столбце 1 (т.е. v _{i 1} для каждого i в {1, ..., r -1}). Теперь, поскольку E₁₁ содержит все столбцы, нам нужно как минимум r - 2 дополнительных вершины - по одной вершине для каждого столбца {2, ..., r }. Всего для каждой трансверсали требуется не менее 2 r -3 вершин.

Алгоритмы [ править ]

Доказательство Хакселла неконструктивно. Однако Чидамбарам Аннамалай доказал, что идеальное соответствие может быть эффективно найдено при немного более сильных условиях. ^[8]

Для каждого фиксированного выбора и существует алгоритм, который находит Y -совершенное соответствие в каждом r- равномерном двудольном гиперграфе, удовлетворяющем для каждого подмножества Y ₀ из Y :${\displaystyle r\geq 2}$${\displaystyle \epsilon >0}$

${\displaystyle \tau (H_{H}(Y_{0}))\geq (2r-3+\epsilon )\cdot (|Y_{0}|-1)+1}$

Фактически, в любом r- однородном гиперграфе алгоритм находит либо Y -совершенное сопоставление, либо подмножество Y _0, нарушающее указанное выше неравенство.

Алгоритм работает полиномиально по времени размером H , но экспоненциально по r и 1 / ε .

Это открытый вопрос, существует ли алгоритм с полиномом времени выполнения по r или 1 / ε (или обоим).

Подобные алгоритмы применялись для решения проблем справедливого распределения предметов , в частности, проблемы Санта-Клауса . ^{[9] [10] [11]}

Условия Ахарони – Хакселла: наименьшие наборы закреплений [ править ]

Будем говорить , что множество K ребер штифтами другой набор F ребер , если каждое ребро F пересекает некоторое ребро в K . ^[6] ширина гиперграфа H = ( V , E ), обозначается ш ( Н ), является наименьшим размером подмножества Е , что штифты E . ^[7] Ширина согласования гиперграфа H , обозначаются MW ( H ) является максимальной, по всем паросочетаниям М в Н, Из подмножества Е , что штифты M . ^[12] Так как Е содержит все паросочетаний в Е , ширина Н, очевидно , по крайней мере , столь же большой как согласующего-шириной Н .

Ахарони и Хакселл доказали следующее условие:

Пусть H = ( X + Y , E ) двудольный гиперграф. Предположим, что для любого подмножества Y ₀ из Y выполняется неравенство

${\displaystyle mw(N_{H}(Y_{0}))\geq |Y_{0}|}$

[другими словами: N _H ( Y ₀ ) содержит соответствие M ( Y ₀ ) такое, что по крайней мере | Y ₀ | непересекающиеся ребра из N _H ( Y ₀ ) необходимы для закрепления M ( Y ₀ )]. Тогда H допускает Y -совершенное паросочетание. ^{[6] : Теорема 1.1.}

Позже они расширили это условие несколькими способами, которые позже были расширены Мешуламом следующим образом:

Пусть H = ( X + Y , E ) двудольный гиперграф. Предположим, что для каждого подмножества Y ₀ в Y выполняется хотя бы одно из следующих условий:

${\displaystyle mw(N_{H}(Y_{0}))\geq |Y_{0}|}$ или же ${\displaystyle w(N_{H}(Y_{0}))\geq 2|Y_{0}|-1}$

Тогда H допускает Y -совершенное паросочетание. ^{[7] : Теорема 1.4.}

В простых графиках [ править ]

В двудольном простом графе соседний гиперграф содержит только синглтоны - по синглету для каждого соседа Y ₀ . Поскольку синглтоны не пересекаются, весь набор соседей N _H ( Y ₀ ) является совпадением, и его единственный набор пиннинга - это сам набор N _H ( Y ₀ ), т. Е. Ширина согласования N _H ( Y ₀ ) есть | N _H ( Y ₀ ) |, а его ширина такая же: w ( N _H ( Y ₀ )) = mw ( N _H ( Y ₀)) = | N _H ( Y ₀ ) |. Таким образом, оба вышеуказанных условия эквивалентны условию брака Холла.

Примеры [ править ]

Мы рассматриваем несколько двудольных графов с Y = {1, 2} и X = {A, B; а, б, в}. Условие Ахарони – Хакселла тривиально выполняется для пустого множества. Это верно для подмножеств размера 1 тогда и только тогда, когда каждая вершина в Y содержится хотя бы в одном ребре, что легко проверить. Остается проверить подмножество Y сам.

1. H = {{1, A, a}; {2, B, b}; {2, Б, в}}. Здесь N _H ( Y ) = {{A, a}, {B, b}, {B, c}}. Его ширина соответствия составляет не менее 2, так как оно содержит соответствие размера 2, например {{A, a}, {B, b}}, которое не может быть закреплено каким-либо одним ребром из N _H ( Y ₀ ). В самом деле, H допускает Y -совершенное сопоставление, например {{1, A, a}; {2, Б, б}}.
2. H = {{1, A, a}; {1, B, b}; {2, A, b}, {2, B, a}}. Здесь N _H ( Y ) = {{A, a}, {B, b}, {A, b}, {B, a}}. Его ширина соответствия равна 1: оно содержит соответствие размера 2, например {{A, a}, {B, b}}, но это соответствие может быть закреплено одним ребром, например {A, b}. Другое соответствие размера 2 - это {{A, b}, {B, a}}, но оно также может быть закреплено одним ребром {A, a}. Хотя N _H ( Y ) больше, чем в примере 1, его ширина соответствия меньше - в частности, меньше | Y |, Следовательно, достаточное условие Ахарони – Хакселла не выполняется. В самом деле, H не допускает Y -совершенного паросочетания.
3. H = {{1, A, a}, {1, A, b}; {1, B, a}, {1, B, b}; {2, A, a}, {2, A, b}; {2, B, a}, {2, B, b}}. Здесь, как и в предыдущем примере, N _H ( Y ) = {{A, a}, {B, b}, {A, b}, {B, a}}, поэтому достаточное условие Ахарони – Хакселла нарушается. Ширина N _H ( Y ) равна 2, поскольку она закреплена, например, множеством {{A, a}, {B, b}}, поэтому более слабое условие Мешулама также нарушается. Однако этот H допускает Y -совершенное сопоставление, например {{1, A, a}; {2, B, b}}, что показывает, что эти условия не являются необходимыми.

Формулировка семейства сетов [ править ]

Рассмотрим двудольный гиперграф H = ( X + Y , E ), где Y = {1, ..., m }. Теоремы Холла типа не заботятся о множестве Y самом - они заботятся только о соседях элементов Y . Следовательно, H можно представить как набор семейств множеств { H ₁ , ..., H _m }, где для каждого i в [ m ] H _i  : = N _H ({ i }) = семейство множеств соседи i . Для каждого подмножества Y₀ из Y , множество семья Н _Н ( Y ₀ ) представляет собой объединение множества-семейства H _я для I в Y _0. A согласованиях совершенных в Н представляет собой набор-семейство размера м , где для каждого я в [ m ], семейство множеств H _i представлено множеством R _i в H _i , а репрезентативные множества R _i попарно не пересекаются.

В этой терминологии теорему Аарони – Хакселла можно сформулировать следующим образом.

Пусть A = { H ₁ , ..., H _m } набор семейств множеств. Для каждого суб-коллекции B из A , рассмотрим множество семью U B - объединение всех в Н _я в B . Предположим, что для каждого поднабора B в A этот U B содержит соответствие M ( B ) такое, что по крайней мере | B | непересекающиеся подмножества из U B необходимы для закрепления M ( B ). Тогда A допускает систему непересекающихся представителей.

Необходимое и достаточное условие [ править ]

Пусть H = ( X + Y , E ) двудольный гиперграф. Следующие утверждения эквивалентны: ^{[6] : Теорема 4.1.}

• H допускает Y -совершенное соответствие.
• Существует присвоение соответствия M ( Y ₀ ) в N _H ( Y ₀ ) для каждого подмножества Y ₀ из Y , так что для закрепления M ( Y ₀ ) требуется как минимум | Y ₀ | непересекающиеся ребра из U { M ( Y ₁ ): Y ₁ является подмножеством Y ₀ }.

В формулировке семейства множеств: пусть A = { H ₁ , ..., H _m } набор семейств множеств. Следующие варианты эквивалентны:

• A допускает систему непересекающихся представителей;
• Существует назначение согласующего M ( B ) в U B для каждого суб-коллекции B из A , такое , что для закрепления M ( B ), по крайней мере , | B | ребра из U { M ( C ): C является подколлекцией B }.

Примеры [ править ]

Рассмотрим пример №3 выше: H = {{1, A, a}, {1, A, b}; {1, B, a}, {1, B, b}; {2, A, a}, {2, A, b}; {2, B, a}, {2, B, b}}. Поскольку он допускает Y -совершенное сопоставление, он должен удовлетворять необходимому условию. Действительно, рассмотрим следующее присвоение подмножеств Y :

• М ({1}) = {А, а}
• M ({2}) = {B, b}
• M ({1,2}) = {{A, a}, {B, b}}

В достаточном условии для закрепления M ({1,2}) требуется не менее двух ребер из N _H ( Y ) = {{A, a}, {B, b}, {A, b}, {B, a}} ; это не выдержало.

Но в необходимом условии для закрепления M ({1,2}) требовалось по крайней мере два ребра из M ({1}) u M ({2}) u M ({1,2}) = {{A, a} , {B, b}}; это держится.

Следовательно, необходимое + достаточное условие выполнено.

Доказательство [ править ]

Доказательство топологическое и использует лемму Спернера . Интересно, что из этого следует новое топологическое доказательство исходной теоремы Холла. ^[13]

Во-первых, предположим, что никакие две вершины в Y не имеют в точности одного и того же соседа (это без ограничения общности, поскольку для каждого элемента y из Y можно добавить фиктивную вершину ко всем соседям y ).

Пусть Y = {1, ..., m }. Они рассматривают симплекс с m -вершиной и доказывают, что он допускает триангуляцию T с некоторыми особыми свойствами, которые они называют экономически-иерархической триангуляцией . Затем они маркируют каждую вершину T гиперребром из N _H ( Y ) следующим образом:

• (a) Для каждого i в Y главная вершина i симплекса помечена некоторым гиперребром из паросочетания M ({ i }).
• (b) Каждая вершина T на грани, натянутая на подмножество Y ₀ из Y , помечена некоторым гиперребром из паросочетания M ( Y ₀ ).
• (c) Для каждых двух соседних вершин T их метки либо идентичны, либо не пересекаются.

Их достаточное условие означает, что такая разметка существует. Затем они окрашивают каждую вершину v из T в цвет i , так что гиперребро, назначенное v, является соседом i .

Условия (а) и (б) гарантируют, что эта раскраска удовлетворяет краевому условию Спернера. Следовательно, существует полностью помеченный симплекс. В этом симплексе m гиперребер, каждое из которых является соседом другого элемента Y , поэтому они не должны пересекаться. Это желаемое Y- идеальное совпадение.

Расширения [ править ]

Теорема Ахарони – Хакселла имеет дефектную версию. Он используется для доказательства гипотезы Райзера при r = 3. ^[12]

Состояние Мешулама [ править ]

Игра Мешулама - это игра, в которую играют два игрока на графе. Один игрок - CON - хочет доказать, что граф имеет высокую гомологическую связность . Другой игрок - НЕТ - хочет доказать обратное. CON предлагает ребра для NON один за другим; NON может либо отсоединить край, либо взорвать его; взрыв удаляет граничные конечные точки и всех их соседей. Оценка CON - это количество взрывов, когда все вершины исчезли, или бесконечность, если остались некоторые изолированные вершины. Ценность игры на данном графе G (оценка CON, когда оба игрока играют оптимально) обозначается Ψ ( G ). Игра Мешулама изучалась, в частности, для линейных графов гиперграфов : линейный граф H , обозначенный L ( H), Представляет собой график , в котором вершина ребро Н , и две таких вершины соединены тогда и только тогда их соответствующие ребра пересекаются в H . Мешулам доказал следующее условие:

Пусть H = ( X + Y , E ) двудольный гиперграф. Предположим, что для любого подмножества Y ₀ из Y выполняется следующее условие:

${\displaystyle \Psi (L(N_{H}(Y_{0})))\geq |Y_{0}|}$.

Где N _H ( Y ₀ ) считается мульти-гиперграфом (т. Е. Он может содержать одно и то же гиперребро несколько раз, если он является соседом нескольких различных элементов Y ₀ ). Тогда H допускает Y -совершенное паросочетание. ^[14]

В простых графиках [ править ]

В двудольном простом графе соседний гиперграф содержит только синглтоны - синглтоны для каждого соседа Y ₀ (некоторые синглтоны появляются более одного раза - если они являются соседями разных элементов Y ₀ ). Таким образом, его линейный граф содержит | N _H ( Y ₀ ) | вершинно-непересекающиеся клики - клика для каждого элемента. Следовательно, когда играют в игру Мешулама, NON не нуждается в | N _H ( Y ₀ ) | взрывы, чтобы уничтожить все L ( N _H ( Y ₀ )), поэтому Ψ (L ( N _H ( Y ₀ )) = | N _H( Y ₀ ) |. Таким образом, состояние Мешулама становится условием брака Холла.

Примеры [ править ]

Мы рассматриваем несколько двудольных графов с Y = {1, 2} и X = {A, B; а, б, в}. Условие Мешулама тривиально выполняется для пустого множества. Это верно для подмножеств размера 1 тогда и только тогда, когда соседний граф каждой вершины в Y непуст (поэтому для уничтожения требуется по крайней мере один взрыв), что легко проверить. Остается проверить подмножество Y сам.

1. H = {{1, A, a}; {2, B, b}; {2, Б, в}}. Здесь N _H ( Y ) = {{A, a}, {B, b}, {B, c}}. Граф L ( N _H ( Y )) имеет три вершины: Aa, Bb и Bc. Подключены только два последних; вершина Aa изолирована. Следовательно, Ψ (L ( N _H ( Y )) = ∞. Действительно, H допускает Y -совершенное паросочетание, например {{1, A, a}; {2, B, b}}.
2. H = {{1, A, a}; {1, B, b}; {2, A, b}, {2, B, a}}. Здесь L ( N _H ( Y )) имеет четыре вершины: Aa, Bb, Ab, Ba и четыре ребра: {Aa, Ab}, {Aa, Ba}, {Bb, Ba}, {Bb, Ab}. Для любого ребра, которое предлагает CON, NON может взорвать его и уничтожить все вершины. Следовательно, Ψ (L ( N _H ( Y )) = 1. Действительно, H не допускает Y -совершенного паросочетания.
3. H = {{1, A, a}, {1, A, b}; {1, B, a}, {1, B, b}; {2, A, a}, {2, A, b}; {2, B, a}, {2, B, b}}. Здесь N _H ( Y ) то же, что и в предыдущем примере, поэтому достаточное условие Мешулама нарушается. Однако этот H допускает Y -совершенное сопоставление, например {{1, A, a}; {2, B, b}}, что показывает, что в этом условии нет необходимости.

Необходимые и достаточные условия использования Ψ неизвестны.

Дополнительные условия из сопоставлений радуги [ править ]

Соответствия радуги комбинационные в простом графе, в котором каждое ребро имеет другой «цвет». Рассматривая цвета как вершины в множестве Y , можно увидеть, что соответствие радуги на самом деле является соответствием в двудольном гиперграфе. Таким образом, несколько достаточных условий существования большого радужного паросочетания можно перевести в условия существования большого паросочетания в гиперграфе.

Следующие результаты относятся к трехчастному гиперграфу s, в котором каждая из 3 частей содержит ровно n вершин, степень каждой вершины равна точно n , а множество соседей каждой вершины является паросочетанием (далее «n-трехчастный гиперграф») :

• Каждый n -трехчастный гиперграф имеет паросочетание размера 2 n / 3. ^[15]
• Каждый n -трехчастный гиперграф имеет сопоставление размера n - sqrt ( n ). ^[16]
• Каждый n -трехчастный гиперграф имеет сопоставление размера n - 11 log ₂ ² ( n ). ^[17]
• HJ Райзер высказал предположение , что, когда п является нечетным , каждый п -tripartite-Гиперграф имеет согласование размера п . ^[18]
• С. К. Штейн и Бруальди высказал предположение , что, когда п является даже каждый п -tripartite-Гиперграф имеет соответствие размера п -1. ^[19] (известно, что соответствие размера n в этом случае может не существовать).
• Более общая гипотеза Стейна состоит в том, что соответствие размера n -1 существует даже без требования, чтобы набор соседей каждой вершины в Y был паросочетанием. ^[18]

Следующие результаты относятся к более общим двудольным гиперграфам:

• Любой трехчастный гиперграф (X ₁ + X ₂ + Y, E), в котором | Y | = 2 n -1, степень каждой вершины y в Y равна n , и набор соседей y является сопоставлением, имеет сопоставление размера n . ^[20] 2 n -1 является наилучшим возможным: если | Y | = 2 n -2, то максимальное соответствие может иметь размер n -1.
• Любой двудольный гиперграф (X + Y, E), в котором | Y | = 3 n -2, степень каждой вершины y в Y равна n , и набор соседей y является сопоставлением, имеющим сопоставление размера n . ^[20] Неизвестно, насколько это возможно. Для четного n известно только, что требуется 2 n ; для нечетных n известно только, что требуется 2 n -1.

См. Также [ править ]

• Независимый от радуги набор

Условие Конфорти-Корнуехолса-Капура-Вусковича: сбалансированные гиперграфы [ править ]

Сбалансированный гиперграф является альтернативным обобщением двудольного графа: это Гиперграф , в котором каждый нечетный цикл С из Н имеет край , содержащий по меньшей мере три вершины C .

Пусть H = (V, E ) - сбалансированный гиперграф. Следующие варианты эквивалентны: ^{[21] [22]}

• H допускает идеальное совпадение (т. Е. Совпадение, в котором совпадает каждая вершина).
• Для всех непересекающихся множеств вершин V ₁ , V ₂ , если | V ₁ | > | V ₂ |, то существует такое ребро e в E , что (эквивалентно: если для всех ребер e в E , то | V ₂ | ≥ | V ₁ |).${\displaystyle |e\cap V_{1}|>|e\cap V_{2}|}$${\displaystyle |e\cap V_{2}|\geq |e\cap V_{1}|}$

В простых графиках [ править ]

Простой граф двудольный тогда и только тогда, когда он сбалансирован (не содержит нечетных циклов и ребер с тремя вершинами).

Пусть G = ( X + Y , E ) двудольный граф. Пусть X ₀ подмножество X и Y ₀ подмножество Y . Условие « для всех ребер e в E » означает, что X ₀ содержит всех соседей вершин Y _0. Следовательно, условие CCKV становится:${\displaystyle |e\cap X_{0}|\geq |e\cap Y_{0}|}$

«Если подмножество X ₀ из X содержит множество N _H ( Y ₀ ), то | X ₀ | ≥ | Y ₀ |».

Это эквивалентно условию Холла.

См. Также [ править ]

• Совершенное сопоставление в гиперграфах высокой степени - представляет другие достаточные условия существования идеального сопоставления, основанные только на степени вершин.

Ссылки [ править ]