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

В математической области теории графов теоремы Холла для гиперграфов представляют собой несколько обобщений теоремы Холла о браке с графов на гиперграфы . Такие теоремы доказала Офра Кесслер. ^[1]^[2] Рон Ахарони , ^[3]^[4] Пенни Хакселл , ^[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$ входит ровно в одно гиперребро $M$ . Это определение сводится к стандартному определению $Y$ -совершенного паросочетания в двудольном графе.

3. Соседи . Для двудольного гиперграфа $H = (X + Y, E)$ и подмножества $Y 0$ из $Y$ соседями $Y 0$ являются подмножества $X$ , которые имеют общие гиперребра с вершинами $Y 0$ . Формально:

N_{H}(Y_{0}):=\{X_{0}\subseteq X~~|~~\exists y_{0}\in Y_{0}:~\{y_{0}\}\cup X_{0}\in E\}.

Например, в гиперграфе из точки 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 0$ . В двудольном гиперграфе каждый сосед представляет собой множество — соседи — это подмножества $X$ , которые «смежны» с одной или несколькими вершинами $Y 0$ .

Поскольку $N H (Y0 X)$ содержит только подмножества $X$ , можно определить гиперграф, в котором множество вершин — это $а$ множество ребер $NH — (Y0,)$ . Назовем его окрестностью-гиперграфом $Y 0$ и обозначим:

H_{H}(Y_{0}):=(X,N_{H}(Y_{0})).

Обратите внимание, что если $H$ — простой двудольный граф, гиперграф окрестностей каждого $Y 0$ содержит только соседей $Y 0$ в $X$ , каждый из которых имеет петлю.

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

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

{ {1, а, А}, {2, а, В} }

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

{ {1, а, А}, {1, б, В}, {2, а, В}, {2, б, А} }

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

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

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

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

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

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

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

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

Для двудольного простого графа $r = 2$ и условие Ахарони принимает вид:

\nu (H_{H}(Y_{0}))\geq |Y_{0}|.

Более того, гиперграф окрестности (как определено в пункте 3 выше) содержит только одиночные элементы - одиночный элемент для каждого соседа $Y 0$ . Поскольку синглтоны не пересекаются, весь набор синглтонов является паросочетанием. Следовательно, $ν (ЧАС)) = (Y 0 | N ЧАС (Y 0) | =$ количество соседей $Y 0$ . Таким образом, условие Ахарони для каждого подмножества $Y 0$ из $Y$ становится следующим :

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

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

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

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

$Y = {1,..., м};$
E — это объединение E1 _i , …, Em _: (где E _i — множество гиперребер, содержащих вершину ) , и
- Для каждого $i$ из ${1, \dots, m - 1}$ $E i$ содержит $r - 1$ непересекающиеся гиперребра размера $r$ : $\{i,x_{i,1,1},\ldots ,x_{i,1,r-1}\},\ldots ,\{i,x_{i,r-1,1},\ldots ,x_{i,r-1,r-1}\}.$
- $E m$ содержит $m - 1$ гиперребро размера $r$ : $\{m,x_{1,1,1},\ldots ,x_{1,r-1,r-1},\},\ldots ,\{m,x_{m-1,1,1},\ldots ,x_{m-1,r-1,1}\}$

что ребро $i$ в $Em Обратите внимание ,$ пересекает все ребра в $E i$ .

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

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

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

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

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

Наибольший размер дробного паросочетания в $H$ обозначается $ν *(H)$ . Очевидно, $ν *(ЧАС) \geq ν (ЧАС)$ . Предположим, что для каждого подмножества $Y 0$ из $Y$ выполняется следующее более слабое неравенство:

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

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

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

Условие Хакселла: наименьшая трансверсальная

Трансверсаль ) в (также называемая вершинным покрытием или набором попаданий гиперграфе $H = (V, E)$ это подмножество $U$ из $V$ такое, что каждое гиперребро в $E$ содержит хотя бы одну вершину из $U.$ — Наименьший размер трансверсали в $H$ обозначается $τ (H)$ .

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

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

Другими словами: окрестность-гиперграф $Y 0$ не имеет трансверсали размера $(2 r - 3)(Y 0 - 1)$ или меньше.

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

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

Для двудольного простого графа $r = 2,$ поэтому $2 r - 3 = 1$ , и условие Хакселла принимает вид:

\tau (H_{H}(Y_{0}))\geq |Y_{0}|.

Более того, гиперграф окрестности (как определено в пункте 3 выше) содержит только одиночные элементы - одиночный элемент для каждого соседа $Y 0$ . В гиперграфе одиночек трансверсаль должна содержать все вершины. Следовательно, $τ (ЧАС)) = (Y 0 | N ЧАС (Y 0) | =$ количество соседей $Y 0$ . Таким образом, условие Хакселла для каждого подмножества $Y 0$ из $Y$ становится следующим :

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

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

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

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

$Y=\{0,1\}$
$X=\{x_{ij}:1\leq i,j\leq r-1\}$ [так $| Х | = (р - 1) 2$ ].

$E=E_{0}\cup E_{1},$ $E=E_{0}\cup E_{1},$ где:
- $E_{0}=\{\{0,x_{i1},\ldots ,x_{i(r-1)}\}|1\leq i\leq r-1\}$
  [так что $E 0$ содержит $r - 1$ гиперрёбра].
- $E_{1}=\{\{1,x_{1j[1]},\ldots ,x_{(r-1)j[r-1]}\}|1\leq j[k]\leq r-1$
  для $1\leq k\leq r-1\}$
  [так что $E 1$ содержит $(r - 1) р -1$ гиперребра].

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

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

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

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

E_{00}=\{\{x_{i1},\ldots ,x_{i(r-1)}\}|1\leq i\leq r-1\}

E_{11}=\{\{x_{1j[1]},\ldots ,x_{(r-1)j[r-1]}\}|1\leq j[k]\leq r-1

для

1\leq k\leq r-1\}

Можно визуализировать вершины $X$ , расположенные на $сетке (r - 1) \times (r - 1)$ . Гиперребрами $E 00$ являются $r - 1$ ряды. Гиперребрами $E 11$ являются $(r - 1) р -1$ выбор одного элемента в каждой строке и каждом столбце. Для покрытия гиперребер $E 10$ нам понадобится $r - 1$ вершин – по одной вершине в каждой строке. Поскольку все столбцы в конструкции симметричны, можно считать, что мы берем все вершины в столбце 1 (т. е. $v i 1$ для каждого $i$ из ${1, \dots, r - 1})$ . Теперь, поскольку $E11 дополнительных вершин - по$ содержит все столбцы, нам нужно как минимум $r - 2$ одной вершине на каждый столбец ${2, \dots, r}.$ Всего для каждой трансверсали требуется не менее $2 r - 3$ вершин.

Алгоритмы

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

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

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

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

Алгоритм работает за время, полиномиальное по размеру $H$ , но экспоненциальное по $r$ и $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1 ⁄ ε$ .

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

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

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

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

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

Пусть $H = (X + Y, E)$ — двудольный гиперграф. Предположим, что для каждого подмножества $Y 0$ из $Y$ выполняется следующее неравенство:
$mw(N_{H}(Y_{0}))\geq |Y_{0}|$
[другими словами: $N H (Y 0)$ содержит паросочетание $M(Y 0)$ такое, что по крайней мере $| Д 0 |$ непересекающиеся ребра из $N H (Y 0)$ необходимы для закрепления $M (Y 0)$ ]. Тогда $H$ допускает $Y$ -совершенное паросочетание. ^[6]^{: Теорема 1.1}

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

Пусть $H = (X + Y, E)$ — двудольный гиперграф. Предположим, что для каждого подмножества $Y 0$ из $Y$ выполняется хотя бы одно из следующих условий:
$mw(N_{H}(Y_{0}))\geq |Y_{0}|$ или $w(N_{H}(Y_{0}))\geq 2|Y_{0}|-1$
Тогда $H$ допускает $Y$ -совершенное паросочетание. ^[7]^{: Теорема 1.4}

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

В двудольном простом графе гиперграф окрестностей содержит только одиночные элементы - одиночный элемент для каждого соседа $Y 0$ . Поскольку одиночки не пересекаются, весь набор соседей $N H (Y 0)$ является паросочетанием, и его единственным набором закрепления является сам набор $N H (Y 0)$ , т. е. ширина сопоставления $N H (Y 0 ) . )$ | $ N ЧАС (Y 0) |$ , и его ширина одинакова:

w(N_{H}(Y_{0}))=mw(N_{H}(Y_{0}))=|N_{H}(Y_{0})|.

Таким образом, оба вышеуказанных условия эквивалентны условию брака Холла.

Примеры

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

$Н = { {1,А,а}; {2,В,б}; {2,Б,с} }.$ Здесь $N H (Y) = { {A,a}, {B,b}, {B,c} }.$ Его ширина сопоставления не менее 2, поскольку оно содержит паросочетание размера 2, например ${{A,a}, {B,b}},$ которое не может быть закреплено ни одним ребром из $N H (Y 0)$ . Действительно, H допускает $Y$ -совершенное паросочетание, например ${ {1,A,a}; {2,В,б} }.$
$Н = { {1,А,а}; {1,Б,Б}; {2,А,б}, {2,В,а} }.$ Здесь $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, его ширина соответствия меньше - в частности, она меньше $| Ю |$ . Следовательно, достаточное условие Ахарони–Хакселла не выполнено. Действительно, $H$ не допускает $Y$ -совершенного паросочетания.
$Н = { {1,А,а}, {1,А,b}; {1,В,а}, {1,В,б}; {2,А,а}, {2,А,б}; {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, \dots, m}.$ Теоремы типа Холла не заботятся о самом множестве $Y$ — их интересуют только соседи элементов $Y$ . Поэтому $H$ можно представить как совокупность семейств множеств ${H 1, \dots, H m},$ где для каждого $i$ в $[m]$ , $H i := N H ({i}) =$ семейство множеств соседей $я$ . Для каждого подмножества $Y 0$ из $Y$ семейство множеств $N H (Y 0)$ является объединением семейств множеств $H i$ для $i$ в $Y 0$ . Идеальное паросочетание в $H$ — это семейство множеств размера $,$ где для каждого $i$ в $[m]$ множеств $Hi семейство$ представлено множеством $Ri .$ в $Hi m$ , а репрезентативные множества $R i$ попарно непересекаются .

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

Пусть $A = {H 1, \dots, H m}$ — совокупность семейств множеств. Для каждой подколлекции $B$ из $A$ рассмотрим семейство множеств $\cup B$ — объединение всех $H i$ в $B$ . Предположим, что для каждой подгруппы $B$ из $A$ эта $\cup B$ содержит паросочетание $M (B)$ такое, что по крайней мере $| Б |$ непересекающиеся подмножества $\cup B.$ требуются $для закрепления M (B)$ из Тогда $A$ допускает систему непересекающихся представителей.

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

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

$H$ допускает $Y$ -совершенное паросочетание.
Существует назначение паросочетания $M (Y 0)$ в $N H (Y 0)$ для каждого подмножества $Y 0$ из $Y$ , такое, что для закрепления $M (Y 0)$ требуется как минимум $| 0 |$ непересекающиеся ребра из $\cup {M (Y 1): Y 1$ является подмножеством $Y 0}.$

В формулировке семейства множеств: пусть $A = {H 1, \dots, H m}$ — совокупность семейств множеств. Следующие действия эквивалентны:

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

Примеры

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

$M({1}) = {A,a}$
$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}) \cup M({2}) \cup M({1,2}) = { {A,a} , {B,b} };$ оно держится.

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

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

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

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

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

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

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

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

Расширения

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

Условия Мешулама - топологические теоремы Холла

В абстрактных симплициальных комплексах

Пусть $V$ — множество вершин. Пусть $C$ — абстрактный симплициальный комплекс на $V$ . Пусть $V y$ (для $y$ в $Y$ ) — подмножества $V$ . CV $-$ трансверсаль — это множество из $C$ (элемент $C$ ), пересечение которого с каждым $V y$ содержит ровно одну вершину. Для каждого подмножества $Y 0$ из $Y$ пусть

V_{Y_{0}}:=\bigcup _{y\in Y_{0}}V_{y}.

Предположим, что для каждого подмножества $Y 0$ из $Y$ гомологическая связность плюс 2 подкомплекса, индуцированного $V_{Y_{0}}$ по крайней мере $| Д 0 |$ , то есть:

\eta _{H}(C[V_{Y_{0}}])\geq |Y_{0}|.

Тогда существует $CV-$ трансверсаль. существует множество $То есть: в C$ , которое пересекает каждый $V y$ ровно на один элемент. ^[14] Эта теорема имеет дефектную версию. ^[15] Если для каждого подмножества $Y 0$ из $Y$ :

\eta _{H}(C[V_{Y_{0}}])\geq |Y_{0}|-d,

тогда существует частичная $C$ -трансверсаль, пересекающая некоторую $| Ю | - d$ задает по 1 элементу, а остальные не более чем по 1 элементу. В более общем смысле, если $g$ — функция натуральных целых чисел, удовлетворяющая $g (z + 1) \leq g (z) + 1$ , и для каждого подмножества $Y 0$ из $Y$ :

\eta _{H}(C[V_{Y_{0}}])\geq g(|Y_{0}|),

существует множество $тогда в C$ , которое пересекает не менее $g (| Y |)$ из $V y$ по одному элементу, а остальные не более чем по одному элементу.

Игра Мешулама

Использование приведенной выше теоремы требует некоторых нижних оценок гомологической связности. Одну такую нижнюю оценку дает игра Мешулама . Это игра, в которую играют два игрока на графике. Один игрок — CON — хочет доказать, что граф имеет высокую гомологическую связность . Другой игрок – НЕ – хочет доказать обратное. CON предлагает ребра NON одно за другим; NON может либо отключить ребро, либо взорвать его; взрыв удаляет конечные точки ребер и всех их соседей. Оценка CON — это количество взрывов, когда все вершины исчезли, или бесконечность, если остаются некоторые изолированные вершины. Ценность игры на данном графе $G$ (оценка CON, когда оба игрока играют оптимально) обозначается $Ψ(G)$ . получения нижней оценки гомологической связности комплекса независимости G $Это число можно использовать для$ , обозначаемого ⁠ ${\mathcal {I}}(G)$ ⁠ :

\eta _{H}({\mathcal {I}}(G))\geq \Psi (G).

Таким образом, из приведенной выше теоремы следует следующее. Пусть $V$ — множество вершин. Пусть $G —$ граф на $V$ . Предположим, что для каждого подмножества $Y 0$ из $Y$ :

\Psi (G[V_{Y_{0}}])\geq |Y_{0}|.

существует независимое множество $Тогда в G$ , которое пересекает каждый $V y$ ровно по одному элементу.

В простых двудольных графах

Пусть $H$ двудольный граф с частями $X$ и $Y.$ — Пусть $V$ множество ребер H $—$ . Пусть $G L(H)$ линейный график H. $=$ = Тогда комплекс независимости ⁠ ${\mathcal {I}}(L(H))$ ⁠ равен паросочетающему комплексу H, обозначаемому ⁠ ${\mathcal {M}}(H)$ ⁠ . Это симплициальный комплекс на ребрах $H$ , элементами которого являются все паросочетания на $H$ . Для каждой вершины $y$ в $Y$ пусть $V y$ — множество ребер, смежных с $y$ (обратите внимание, что $V y$ — подмножество $V$ ). Тогда для каждого подмножества $Y 0$ из $Y$ индуцированный подграф $G[V_{Y_{0}}]$ содержит клику для каждого соседа $Y 0$ (все ребра, смежные с $Y 0$ , которые пересекаются в одной и той же вершине $X$ , образуют клику в линейном графе). Итак, есть $| N ЧАС (Y 0) |$ непересекающиеся клики. Следовательно, когда ведется игра Мешулама, NON не нуждается $| N ЧАС (Y 0) |$ взрывов, чтобы уничтожить все $L(N H (Y 0))$ , поэтому $Ψ(L (N H (Y 0)) = | N H (Y 0) |$ . Таким образом, условие Мешулама

\Psi (G[V_{Y_{0}}])\geq |Y_{0}|

эквивалентно условию брака Холла. Здесь множества $V y$ попарно не пересекаются, поэтому $C$ -трансверсаль содержит уникальный элемент из каждого $V y$ , что эквивалентно $Y$ -насыщающему паросочетанию.

В соответствующих комплексах

Пусть $H$ — двудольный гиперграф, и предположим, что $C$ — его комплекс сопоставления ⁠ ${\mathcal {M}}(H)$ ⁠ . Пусть $H y$ (для $y$ в $Y$ ) — множества ребер $H$ . Для каждого подмножества $Y 0$ из $Y$ , ⁠ ${\mathcal {M}}(H_{Y_{0}})$ ⁠ — множество паросочетаний в подгиперграфе:

\bigcup _{y\in Y_{0}}H_{y}.

Если для каждого подмножества $Y 0$ из $Y$ :

\eta _{H}({\mathcal {M}}(H_{Y_{0}}))\geq |Y_{0}|

Тогда существует паросочетание, которое пересекает каждое множество $H y$ ровно один раз (его еще называют радужным паросочетанием , поскольку каждое $H y$ можно рассматривать как цвет).

Это верно, в частности, если мы определим $H y$ как множество ребер $H,$ содержащее вершину $y$ из $Y$ . В этом случае ⁠ ${\mathcal {M}}(H_{Y_{0}})$ ⁠ эквивалентен $N H (Y 0)$ — мультигиперграфу соседей $Y 0$ («мульти» — поскольку каждому соседу разрешено появляться несколько раз для нескольких разных $y$ ).

Соответствующий комплекс гиперграфа — это в точности комплекс независимости его линейного графа , обозначаемый $L (H)$ . Это граф, вершины которого являются ребрами $H$ , и две такие вершины соединены тогда и только тогда, когда их соответствующие ребра пересекаются $H.$ в Следовательно, из приведенной выше теоремы следует:

\eta _{H}({\mathcal {M}}(H))\geq \Psi (L(H))

Объединение предыдущих неравенств приводит к следующему условию.

Пусть

H = (X + Y, E)

— двудольный гиперграф. Предположим, что для каждого подмножества

Y 0

из

Y

выполняется следующее условие:

\Psi (L(N_{H}(Y_{0})))\geq |Y_{0}|,

где

N H (Y 0)

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

Y 0

). Тогда

H

допускает

Y

-совершенное паросочетание. ^[14]

Примеры

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

$Н = { {1,А,а}; {2,В,б}; {2,Б,с} }.$ Здесь $N H (Y) = { {A,a}, {B,b}, {B,c} }.$ Граф $L(N H (Y))$ имеет три вершины: $Aa, Bb, Bc.$ Только два последних соединены; вершина Аа изолирована. Следовательно, $Ψ(L(N H (Y)) = \infty$ . Действительно, $H$ допускает $Y$ -совершенное паросочетание, например ${ {1,A,a}; {2,B,b} }.$
Н = { {1,А,а}; {1,Б,Б}; {2,А,б}, {2,В,а} }. Здесь $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$ -совершенного паросочетания.
$Н = { {1,А,а}, {1,А,b};$ ${1,В,а}, {1,В,б};$ ${2,А,а}, {2,А,б};$ ${2,B,a}, {2,B,b} }.$ Здесь $N H (Y)$ такое же, как и в предыдущем примере, поэтому достаточное условие Мешулама нарушено. Однако этот $H$ допускает $Y$ -совершенное паросочетание, например ${ {1,A,a}; {2,B,b} },$ что показывает, что это условие не является необходимым.

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

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

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

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

Каждому $n-$ трехчастному гиперграфу соответствует соответствие размера $2 n ⁄ 3$ . ^[16]
Каждый $n-$ трехчастный гиперграф имеет паросочетание размера $n - \sqrt n$ . ^[17]
Каждый $n-$ трехчастный гиперграф имеет паросочетание размера $n - 11 log 2. 2 (н)$ . ^[18]
Каждый $n$ -трехчастный гиперграф имеет соответствие размера $n - O(log n /log log n)$ . ^[19]
Каждый $n-$ трехчастный гиперграф имеет паросочетание размера $n - 1$ . ^[20] (Препринт)
Х. Дж. Райзер предположил, что, когда $n$ нечетно , каждый $n$ -трехчастный гиперграф имеет паросочетание размера $n$ . ^[21]
С. К. Штейн и Бруальди предположили, что, когда $n$ четно , каждый $n$ -трехчастный гиперграф имеет паросочетание размера $n - 1$ . ^[22] (известно, что паросочетания размера $n$ в этом случае может не существовать).
Более общая гипотеза Штейна состоит в том, что паросочетание размера $n - 1$ существует даже без требования, чтобы множество соседей каждой вершины в $Y$ было паросочетанием. ^[21]

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

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

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

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

Пусть $H = (V, E)$ — сбалансированный гиперграф. Следующие действия эквивалентны: ^[24]^[25]

$H$ допускает идеальное паросочетание (т. е. паросочетание, в котором каждая вершина сопоставлена).
Для всех непересекающихся множеств вершин $V 1$ , $V 2$ , если $| В 1 | > | В 2 |$ , то существует ребро $e$ в $E$ такое, что $| е \cap V 1 | > | е \cap V 2 |$ (эквивалентно: если $| e \cap V 2 | \geq | e \cap V 1 |$ для всех ребер $e$ в $E$ , то $| V 2 | \geq | V 1 |$ ).

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

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

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

«Если подмножество $X 0$ из $X$ содержит множество $N H (Y 0)$ , то $| X 0 | \geq | Y 0 |$ ".

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

См. также

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

Ссылки

^ Перейти обратно: ^а ^б ^с Ахарони, Рон; Кесслер, Офра (15 октября 1990 г.). «О возможном распространении теоремы Холла на двудольные гиперграфы» . Дискретная математика . 84 (3): 309–313. дои : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .
^ Перейти обратно: ^а ^б Кесслер, Офра (1989). Соответствия в гиперграфах (докторская диссертация) . Хайфа, Израиль: Технион, Израильский технологический институт.
^ Перейти обратно: ^а ^б Ахарони, Рон (1 декабря 1985 г.). «Соответствия inn-частные-графы». Графы и комбинаторика . 1 (1): 303–304. дои : 10.1007/BF02582958 . ISSN 1435-5914 . S2CID 19258298 .
^ Перейти обратно: ^а ^б ^с Ахарони, Рон (1 июня 1993 г.). «О критерии сопоставимости в гиперграфах». Графы и комбинаторика . 9 (2): 209–212. дои : 10.1007/BF02988309 . ISSN 1435-5914 . S2CID 29126477 .
^ Перейти обратно: ^а ^б Хакселл, ЧП (1 сентября 1995 г.). «Условие сопоставимости в гиперграфах». Графы и комбинаторика . 11 (3): 245–248. дои : 10.1007/bf01793010 . S2CID 28459229 .
^ Перейти обратно: ^а ^б ^с ^д ^и Ахарони, Рон; Хакселл, Пенни (2000). «Теорема Холла для гиперграфов» . Журнал теории графов . 35 (2): 83–88. doi : 10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V . ISSN 1097-0118 .
^ Перейти обратно: ^а ^б ^с Мешулам, Рой (1 января 2001 г.). «Комплекс клик и сопоставление гиперграфов». Комбинаторика . 21 (1): 89–94. дои : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .
^ Аннамалай, Чидамбарам (21 декабря 2015 г.), «Нахождение идеальных совпадений в двудольных гиперграфах», Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 2016 года , Труды Общества промышленной и прикладной математики, стр. 1814–1823, arXiv : 1509.07007 , doi : 10.1137/1.9781611974331.ch126 , ISBN 978-1-61197-433-1
^ Асадпур Араш; Файги Уриэль; Сабери Амин (24 июля 2012 г.). «Санта-Клаус встречает соответствия гиперграфа». Транзакции ACM на алгоритмах . 8 (3): 1–9. дои : 10.1145/2229163.2229168 . S2CID 10281304 .
^ Аннамалай Чидамбарам; Калаитцис Христос; Свенссон Ола (26 мая 2017 г.). «Комбинаторный алгоритм ограниченного справедливого распределения максимума и минимума». Транзакции ACM на алгоритмах . 13 (3): 1–28. arXiv : 1409.0607 . дои : 10.1145/3070694 . S2CID 14749011 .
^ Дэвис, Сами; Ротвосс, Томас; Чжан, Ихао (23 декабря 2019 г.), «Сказка о Санта-Клаусе, гиперграфах и матроидах», Труды симпозиума ACM-SIAM 2020 года по дискретным алгоритмам , Труды Общества промышленной и прикладной математики, стр. 2748–2757, arXiv : 1807.07189 , doi : 10.1137/1.9781611975994.167 , ISBN 978-1-61197-599-4 , S2CID 49880727
^ Перейти обратно: ^а ^б Ахарони, Рон (1 января 2001 г.). «Гипотеза Райзера для трехдольных трехграфов». Комбинаторика . 21 (1): 1–4. дои : 10.1007/s004930170001 . ISSN 1439-6912 . S2CID 13307018 .
^ Калаи, Гил (25 ноября 2012 г.). «С днем рождения, Рон Ахарони!» . Комбинаторика и многое другое . Проверено 30 июня 2020 г.
^ Перейти обратно: ^а ^б Мешулам, Рой (1 мая 2003 г.). «Числа доминирования и гомологии» . Журнал комбинаторной теории . Серия А. 102 (2): 321–330. дои : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165 .
^ Ахарони, Рон; Бергер, Эли; Бриггс, Джозеф; Сегал-Халеви, Эрель; Зербиб, Шира (02.11.2020). «Дробно сбалансированные гиперграфы и радужные теоремы ККМ». arXiv : 2011.01053 [ math.CO ].
^ Коксма, Клаас К. (1 июля 1969). «Нижняя оценка порядка частичной трансверсали в латинском квадрате» . Журнал комбинаторной теории . 7 (1): 94–95. дои : 10.1016/s0021-9800(69)80009-8 . ISSN 0021-9800 .
^ Вулбрайт, Дэвид Э. (1 марта 1978 г.). «Латинский квадрат размера n × n имеет трансверсаль, содержащую как минимум n−n различных символов» . Журнал комбинаторной теории . Серия А. 24 (2): 235–237. дои : 10.1016/0097-3165(78)90009-2 . ISSN 0097-3165 .
^ Хатами, Пуя; Шор, Питер В. (1 октября 2008 г.). «Нижняя оценка длины частичной трансверсали в латинском квадрате» . Журнал комбинаторной теории . Серия А. 115 (7): 1103–1113. дои : 10.1016/j.jcta.2008.01.002 . ISSN 0097-3165 .
^ Киваш, Питер; Покровский, Алексей; Судаков, Бенни; Епремян, Лиана (15.04.2022). «Новые границы гипотезы Райзера и связанных с ней проблем» . Труды Американского математического общества, серия B. 9 (8): 288–321. arXiv : 2005.00526 . дои : 10.1090/btran/92 . ISSN 2330-0000 .
^ Монтгомери, Ричард (2023). «Доказательство гипотезы Райзера-Бруальди-Стейна для больших четных n ». arXiv : 2310.19779 [ math.CO ].
^ Перейти обратно: ^а ^б Ахарони, Рон; Бергер, Эли; Котлар, Дэни; Зив, Ран (04 января 2017 г.). «О догадке камня». Трактаты математического семинара Гамбургского университета . 87 (2): 203–211. дои : 10.1007/s12188-016-0160-3 . ISSN 0025-5858 . S2CID 119139740 .
^ Штейн, Шерман (1 августа 1975 г.). «Трансверсали латинских квадратов и их обобщения» . Тихоокеанский математический журнал . 59 (2): 567–575. дои : 10.2140/pjm.1975.59.567 . ISSN 0030-8730 .
^ Перейти обратно: ^а ^б Ахарони, Рон; Бергер, Эли (25 сентября 2009 г.). «Радужные сопоставления в $r$-частных $r$-графах» . Электронный журнал комбинаторики . 16 (1). дои : 10.37236/208 . ISSN 1077-8926 .
^ Конфорти, Микеле; Корнюжоль, Жерар; Капур, Аджай; Вушкович, Кристина (1 сентября 1996 г.). «Совершенные паросочетания в сбалансированных гиперграфах». Комбинаторика . 16 (3): 325–329. дои : 10.1007/BF01261318 . ISSN 1439-6912 . S2CID 206792822 .
^ Хак, Андреас; Триш, Эберхард (1 июля 2002 г.). «Идеальные соответствия в сбалансированных гиперграфах - комбинаторный подход». Комбинаторика . 22 (3): 409–416. дои : 10.1007/s004930200020 . ISSN 1439-6912 . S2CID 34490040 .

[:1-1] Перейти обратно: ^а ^б ^с Ахарони, Рон; Кесслер, Офра (15 октября 1990 г.). «О возможном распространении теоремы Холла на двудольные гиперграфы» . Дискретная математика . 84 (3): 309–313. дои : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .

[:2-2] Перейти обратно: ^а ^б Кесслер, Офра (1989). Соответствия в гиперграфах (докторская диссертация) . Хайфа, Израиль: Технион, Израильский технологический институт.

[:5-3] Перейти обратно: ^а ^б Ахарони, Рон (1 декабря 1985 г.). «Соответствия inn-частные-графы». Графы и комбинаторика . 1 (1): 303–304. дои : 10.1007/BF02582958 . ISSN 1435-5914 . S2CID 19258298 .

[:3-4] Перейти обратно: ^а ^б ^с Ахарони, Рон (1 июня 1993 г.). «О критерии сопоставимости в гиперграфах». Графы и комбинаторика . 9 (2): 209–212. дои : 10.1007/BF02988309 . ISSN 1435-5914 . S2CID 29126477 .

[:0-5] Перейти обратно: ^а ^б Хакселл, ЧП (1 сентября 1995 г.). «Условие сопоставимости в гиперграфах». Графы и комбинаторика . 11 (3): 245–248. дои : 10.1007/bf01793010 . S2CID 28459229 .

[:4-6] Перейти обратно: ^а ^б ^с ^д ^и Ахарони, Рон; Хакселл, Пенни (2000). «Теорема Холла для гиперграфов» . Журнал теории графов . 35 (2): 83–88. doi : 10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V . ISSN 1097-0118 .

[:7-7] Перейти обратно: ^а ^б ^с Мешулам, Рой (1 января 2001 г.). «Комплекс клик и сопоставление гиперграфов». Комбинаторика . 21 (1): 89–94. дои : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .

[8] Аннамалай, Чидамбарам (21 декабря 2015 г.), «Нахождение идеальных совпадений в двудольных гиперграфах», Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 2016 года , Труды Общества промышленной и прикладной математики, стр. 1814–1823, arXiv : 1509.07007 , doi : 10.1137/1.9781611974331.ch126 , ISBN 978-1-61197-433-1

[9] Асадпур Араш; Файги Уриэль; Сабери Амин (24 июля 2012 г.). «Санта-Клаус встречает соответствия гиперграфа». Транзакции ACM на алгоритмах . 8 (3): 1–9. дои : 10.1145/2229163.2229168 . S2CID 10281304 .

[10] Аннамалай Чидамбарам; Калаитцис Христос; Свенссон Ола (26 мая 2017 г.). «Комбинаторный алгоритм ограниченного справедливого распределения максимума и минимума». Транзакции ACM на алгоритмах . 13 (3): 1–28. arXiv : 1409.0607 . дои : 10.1145/3070694 . S2CID 14749011 .

[11] Дэвис, Сами; Ротвосс, Томас; Чжан, Ихао (23 декабря 2019 г.), «Сказка о Санта-Клаусе, гиперграфах и матроидах», Труды симпозиума ACM-SIAM 2020 года по дискретным алгоритмам , Труды Общества промышленной и прикладной математики, стр. 2748–2757, arXiv : 1807.07189 , doi : 10.1137/1.9781611975994.167 , ISBN 978-1-61197-599-4 , S2CID 49880727

[:6-12] Перейти обратно: ^а ^б Ахарони, Рон (1 января 2001 г.). «Гипотеза Райзера для трехдольных трехграфов». Комбинаторика . 21 (1): 1–4. дои : 10.1007/s004930170001 . ISSN 1439-6912 . S2CID 13307018 .

[13] Калаи, Гил (25 ноября 2012 г.). «С днем рождения, Рон Ахарони!» . Комбинаторика и многое другое . Проверено 30 июня 2020 г.

[:03-14] Перейти обратно: ^а ^б Мешулам, Рой (1 мая 2003 г.). «Числа доминирования и гомологии» . Журнал комбинаторной теории . Серия А. 102 (2): 321–330. дои : 10.1016/S0097-3165(03)00045-1 . ISSN 0097-3165 .

[15] Ахарони, Рон; Бергер, Эли; Бриггс, Джозеф; Сегал-Халеви, Эрель; Зербиб, Шира (02.11.2020). «Дробно сбалансированные гиперграфы и радужные теоремы ККМ». arXiv : 2011.01053 [ math.CO ].

[16] Коксма, Клаас К. (1 июля 1969). «Нижняя оценка порядка частичной трансверсали в латинском квадрате» . Журнал комбинаторной теории . 7 (1): 94–95. дои : 10.1016/s0021-9800(69)80009-8 . ISSN 0021-9800 .

[17] Вулбрайт, Дэвид Э. (1 марта 1978 г.). «Латинский квадрат размера n × n имеет трансверсаль, содержащую как минимум n−n различных символов» . Журнал комбинаторной теории . Серия А. 24 (2): 235–237. дои : 10.1016/0097-3165(78)90009-2 . ISSN 0097-3165 .

[18] Хатами, Пуя; Шор, Питер В. (1 октября 2008 г.). «Нижняя оценка длины частичной трансверсали в латинском квадрате» . Журнал комбинаторной теории . Серия А. 115 (7): 1103–1113. дои : 10.1016/j.jcta.2008.01.002 . ISSN 0097-3165 .

[19] Киваш, Питер; Покровский, Алексей; Судаков, Бенни; Епремян, Лиана (15.04.2022). «Новые границы гипотезы Райзера и связанных с ней проблем» . Труды Американского математического общества, серия B. 9 (8): 288–321. arXiv : 2005.00526 . дои : 10.1090/btran/92 . ISSN 2330-0000 .

[20] Монтгомери, Ричард (2023). «Доказательство гипотезы Райзера-Бруальди-Стейна для больших четных n ». arXiv : 2310.19779 [ math.CO ].

[:022-21] Перейти обратно: ^а ^б Ахарони, Рон; Бергер, Эли; Котлар, Дэни; Зив, Ран (04 января 2017 г.). «О догадке камня». Трактаты математического семинара Гамбургского университета . 87 (2): 203–211. дои : 10.1007/s12188-016-0160-3 . ISSN 0025-5858 . S2CID 119139740 .

[22] Штейн, Шерман (1 августа 1975 г.). «Трансверсали латинских квадратов и их обобщения» . Тихоокеанский математический журнал . 59 (2): 567–575. дои : 10.2140/pjm.1975.59.567 . ISSN 0030-8730 .

[:02-23] Перейти обратно: ^а ^б Ахарони, Рон; Бергер, Эли (25 сентября 2009 г.). «Радужные сопоставления в $r$-частных $r$-графах» . Электронный журнал комбинаторики . 16 (1). дои : 10.37236/208 . ISSN 1077-8926 .

[24] Конфорти, Микеле; Корнюжоль, Жерар; Капур, Аджай; Вушкович, Кристина (1 сентября 1996 г.). «Совершенные паросочетания в сбалансированных гиперграфах». Комбинаторика . 16 (3): 325–329. дои : 10.1007/BF01261318 . ISSN 1439-6912 . S2CID 206792822 .

[25] Хак, Андреас; Триш, Эберхард (1 июля 2002 г.). «Идеальные соответствия в сбалансированных гиперграфах - комбинаторный подход». Комбинаторика . 22 (3): 409–416. дои : 10.1007/s004930200020 . ISSN 1439-6912 . S2CID 34490040 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]