Теоремы холловского типа для гиперграфов - Hall-type theorems for hypergraphs

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

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

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

1. Двудольность: Понятие двудольности может быть расширено на гиперграфы многими способами (см. двудольный гиперграф ). Здесь мы определяем гиперграф как двудольный, если он ровно двухцветный, т.е. его вершины могут быть двухцветными, так что каждое гиперребро содержит ровно одну желтую вершину. Другими словами, V можно разделить на два набора Икс и Y, такое, что каждое гиперребро содержит ровно одну вершину Y.^[1] А двудольный граф является частным случаем, когда каждое ребро содержит ровно одну вершину Y а также ровно одну вершину Икс; в двудольном гиперграфе каждое гиперребро содержит ровно одну вершину Y но может содержать ноль или более вершин Икс. Например, гиперграф (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} и Икс = {2,3,4,6}.

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

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

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

Недостаточность состояния Холла

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

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

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

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

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

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

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

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

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

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

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

В простых графиках

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

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

Это в точности условие брака Холла.

Герметичность

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

• Y = {1, ..., м};
• E это союз E₁, ..., E_м (куда E_я множество гиперребер, содержащее вершину я), и:
  • Для каждого я в 1,...,м-1}, E_я содержит р-1 непересекающиеся гиперребра размера р, {я, Икс_я,1,1, ..., Икс_{я, 1, г−1}}, ..., , {я, Икс_{я, р-1,1}, ..., Икс_{я, г-1, г−1}}.
  • E_м содержит м-1 гиперребра размера р, {м, Икс_1,1,1, ..., Икс_1,р-1,р-1}, ..., , {м, Икс_м-1,1,1, ..., Икс_м-1,р-1,1}. Обратите внимание, что край я в E_м встречает все края в E_я.

Этот ЧАС не допускает Y-идеальное соответствие, так как каждое гиперребро, содержащее м пересекает все гиперребра в E_я для некоторых я < м.

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

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

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

Дробное соответствие

Самый большой размер дробное соответствие в ЧАС обозначается ${ Displaystyle ню ^ {*} (Н)}$. Четко ${ Displaystyle Nu ^ {*} (ЧАС) GEQ Nu (Н)}$. Предположим, что для каждого подмножества Y₀ из Y, выполняется более слабое неравенство:

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

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

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

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

А поперечный (также называемый вершина-крышка или же ударная установка) в гиперграфе ЧАС = (V,E) является подмножеством U из V так что каждое гиперребро в E содержит хотя бы одну вершину U. Наименьший размер трансверсали в ЧАС обозначается ${ Displaystyle тау (Н)}$.

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

${ Displaystyle тау (Н_ {Н} (Y_ {0})) geq (2r-3) cdot (| Y_ {0} | -1) +1}$

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

Потом, ЧАС признает Y-идеальное соответствие (как определено в 2. выше).^{[5]:Теорема 3.}

В простых графиках

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

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

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

Герметичность

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

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

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

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

${ Displaystyle тау (Н_ {Н} (Y_ {0})) geq (2r-3) cdot (| Y_ {0} | -1)}$

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

• E₀₀ = { {Икс_я1, ..., Икс_я(р-1) } | 1 ≤ я ≤ р-1 } .
• E₁₁ = { {Икс_1j[1], ..., Икс_{(р-1) j [r-1]} } | 1 ≤ j[k] ≤ р-1 для 1 ≤ k ≤ р-1 }

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

Алгоритмы

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

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

${ Displaystyle тау (Н_ {Н} (Y_ {0})) geq (2r-3 + epsilon) cdot (| Y_ {0} | -1) +1}$

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

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

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

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

Условия Ахарони – Хакселла: наименьшие наборы пиннинга

Мы говорим, что набор K краев булавки другой набор F ребер, если каждое ребро в F пересекает некоторый край в K.^[6] В ширина гиперграфа ЧАС = (V, E), обозначенный ш(ЧАС), является наименьшим размером подмножества E это булавки E.^[7] В подходящая ширина гиперграфа ЧАС, обозначенный mw(ЧАС) является максимумом по всем сопоставлениям M в ЧАСиз подмножества E это булавки M.^[12] С E содержит все совпадения в E, ширина H, очевидно, не меньше, чем ширина согласования ЧАС.

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

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

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

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

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

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

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

Потом, ЧАС признает Y-идеальное соответствие.^{[7]:Теорема 1.4.}

В простых графиках

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

Примеры

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

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

Набор-семейная формулировка

Рассмотрим двудольный гиперграф ЧАС = (X + Y, E) куда Y = {1,...,м}. Теоремы типа Холла не заботятся о множестве Y себя - они заботятся только о соседях элементов Y. Следовательно ЧАС можно представить в виде набора семейств множеств {ЧАС₁, ..., ЧАС_м}, где для каждого я в [м], ЧАС_я := N_ЧАС({я}) = набор-семейство соседей я. Для каждого подмножества Y₀ из Y, набор-семья N_ЧАС(Y₀) является объединением семейств множеств ЧАС_я для меня в Y_0. А идеальное соответствие в ЧАС это семейство размеров м, где для каждого я в [м], множество-семейство ЧАС_я представлен набором р_я в ЧАС_я, а представительные множества р_я попарно не пересекаются.

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

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

Необходимое и достаточное условие

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

• ЧАС признает Y-идеальное соответствие.
• Есть присвоение соответствия M(Y₀) в N_ЧАС(Y₀) для каждого подмножества Y₀ из Y, так что закрепление M(Y₀) требует, по крайней мере | Y₀| непересекающиеся ребра из U {M(Y₁): Y₁ это подмножество Y₀}.

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

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

Примеры

Рассмотрим пример №3 выше: ЧАС = {{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_ЧАС(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 = {1,...,м}. Они считают м-вершинного симплекса и докажите, что он допускает триангуляцию Т с некоторыми особыми свойствами, которые они называют экономически-иерархическая триангуляция. Затем они маркируют каждую вершину Т с гиперребром из N_ЧАС(Y) следующим образом:

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

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

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

Расширения

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

Состояние Мешулама

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

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

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

Где N_ЧАС(Y₀) считается мультигиперграфом (т.е. он может содержать одно и то же гиперребро несколько раз, если он является соседом нескольких различных элементов Y₀). Потом, ЧАС признает Y-идеальное соответствие.^[14]

В простых графиках

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

Примеры

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

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

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

Больше условий из радужных совпадений

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

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

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

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

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

Смотрите также

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

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

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

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

• ЧАС допускает идеальное соответствие (т. е. соответствие, в котором совпадает каждая вершина).
• Для всех непересекающихся множеств вершин V₁, V₂, если |V₁| > |V₂|, то существует ребро е в E такой, что ${ Displaystyle | е крышка V_ {1} |> | е крышка V_ {2} |}$ (эквивалентно: если ${ Displaystyle | е крышка V_ {2} | geq | е крышка V_ {1} |}$ для всех краев е в E, тогда |V₂| ≥ |V₁|).

В простых графиках

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

Позволять грамм = (Икс+Y, E) - двудольный граф. Позволять Икс₀ быть подмножеством Икс и Y₀ подмножество Y. Условие "${ displaystyle | e cap X_ {0} | geq | e cap Y_ {0} |}$ для всех краев е в E" Значит это Икс₀ содержит всех соседей вершин Y_0- Следовательно, условие CCKV становится:

"Если подмножество Икс₀ из Икс содержит набор N_ЧАС(Y₀), то |Икс₀| ≥ |Y₀|".

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

Смотрите также

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

Рекомендации