Идеальное совпадение в гиперграфах высокой степени

В теории графов идеальное паросочетание в гиперграфах высокой степени — это направление исследования, пытающееся найти достаточные условия существования идеального паросочетания в гиперграфе , основываясь только на степени вершин или их подмножеств.

Введение

Степени и паросочетания в графах

В простом графе $G = (V, E)$ степень вершины $v$ , часто обозначаемая $deg(v)$ или $δ(v)$ , — это количество ребер в $E,$ смежных с $v$ . Минимальная степень графа, часто обозначаемая $deg(G)$ или $δ(v)$ , является минимумом $deg(v)$ по всем вершинам $v$ в $V$ .

Паросочетание в графе — это набор ребер, каждая вершина которого смежна не более чем с одним ребром; идеальное паросочетание — это паросочетание, в котором каждая вершина примыкает ровно к одному ребру. Идеальное паросочетание не всегда существует, поэтому интересно найти достаточные условия, гарантирующие его существование.

Одно из таких условий следует из теоремы Дирака о гамильтоновых циклах . Он гласит, что если $deg( G ) ≥ .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}n / 2$ , то граф допускает гамильтонов цикл ; это означает, что оно допускает идеальное паросочетание. Фактор $n ⁄ 2$ является жестким, поскольку полный двудольный граф на $(n ⁄ 2 - 1, n ⁄ 2 + 1)$ вершин имеет степень $n ⁄ 2 - 1$ , но не допускает полного паросочетания.

Результаты, описанные ниже, направлены на распространение этих результатов с графов на гиперграфы .

Степени в гиперграфах

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

Формально, для каждого целого числа $d \geq 1$ , $deg d (H)$ является минимумом $deg(U)$ над всеми подмножествами $U$ из $V$ , которые содержат ровно $d$ вершин. Таким образом, $deg 1 (H)$ соответствует определению степени простого графа, а именно наименьшей степени одной вершины; $deg 2 (H)$ — наименьшая степень пары вершин; и т. д.

Гиперграф $H = (V, E)$ называется $r$ -равномерным если каждое гиперребро в $E$ содержит ровно $r$ вершин из $V.$ , В $r$ -однородных графах соответствующие значения $d$ равны $1, 2,\dots, r - 1$ . В простом графике $r = 2$ .

Условия на 1-вершинную степень

Ряд авторов доказали достаточные условия для случая $d = 1$ , т. е. условия наименьшей степени одиночной вершины.

Если $H$ — 3-однородный гиперграф на $n$ вершинах, $n$ кратно 3 и
$\deg _{1}(H)\geq {\bigg (}5/9+o(1){\bigg )}{n \choose 2},$
тогда $H$ содержит совершенное паросочетание. ^{[ 1 ]}
Если $H$ — 3-однородный гиперграф на $n$ вершинах, $n$ кратно 3 и
$\deg _{1}(H)\geq {n-1 \choose 2}-{2n/3 \choose 2}+1,$
тогда $H$ содержит совершенное паросочетание — паросочетание размера $k$ . Этот результат является наилучшим из возможных. ^{[ 2 ]}
Если $H$ — 4-однородный гиперграф с $n$ вершинами, $n$ кратно 4 и
$\deg _{1}(H)\geq {n-1 \choose 3}-{3n/4 \choose 3},$
тогда $H$ содержит совершенное паросочетание — паросочетание размера $k$ . Этот результат является наилучшим из возможных. ^{[ 3 ]}
Если $H$ является $r$ -однородным, n кратно $r$ и
$\deg _{1}(H)>{\frac {r-1}{r}}\left({{\binom {n-1}{r-1}}-{\binom {n-kr-1}{r-1}}}\right),$
тогда $H$ содержит паросочетание размера не менее $k + 1$ . В частности, полагая $k = n ⁄ r - 1$ дает это, если
$\deg _{1}(H)>{\frac {r-1}{r}}\left({{\binom {n-1}{r-1}}-1}\right),$
тогда $H$ содержит совершенное паросочетание. ^{[ 4 ]}
Если $H$ - $r$ однородна и $r$ -раздельна, каждая сторона содержит ровно $n$ вершин и
$\deg _{1}(H)>{\frac {r-1}{r}}\left({n^{r-1}-(n-k)^{r-1}}\right),$
тогда $H$ содержит паросочетание размера не менее $k + 1$ . В частности, установка $k = n - 1$ дает, что если
$\deg _{1}(H)>{\frac {r-1}{r}}\left({n^{r-1}-1}\right),$
тогда $H$ содержит совершенное паросочетание. ^{[ 4 ]}

Для сравнения, теорема Дирака о гамильтоновых циклах гласит, что если $H$ 2-равномерен (т. е. простой граф) и

\deg _{1}(H)\geq {n-1 \choose 1}-{n/2 \choose 1}+1=n/2,

тогда $H$ допускает совершенное паросочетание.

Условия на (r-1)-кратную степень

Ряд авторов доказали достаточные условия для случая $d = r - 1$ , т. е. условия наименьшей степени множеств из $r - 1$ вершины в $r$ -однородных гиперграфах с $n$ вершинами.

В r -частных r -однородных гиперграфах

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

Если $\deg _{r-1}(H)\geq n/2+{\sqrt {2n\log _{2}n}}$
и $n \geq 1000$ , то $H$ имеет идеальное паросочетание. Это выражение является наименьшим из возможных с точностью до члена младшего порядка; в частности, $n ⁄ 2$ недостаточно. ^{[ 5 ]}
Если $\deg _{r-1}(H)\geq n/r$
тогда $H$ допускает паросочетание, которое покрывает все вершины, кроме не более чем $r - 2,$ в каждом классе вершин $H$ . $Коэффициент n / r$ , по сути, является наилучшим из возможных. ^{[ 5 ]}
Пусть $V 1, \dots , V r$ — $r$ сторон $H$ . Если степень каждого $(r - 1)$ -кортежа в $V ⁄ V 1$ строго больше, чем $n ⁄ 2$ и степень каждого $(r - 1)$ -кортежа в $V ⁄ V r$ составляет не менее $n ⁄ 2$ , то $H$ допускает совершенное паросочетание. ^{[ 6 ]}

В общем случае r -однородные гиперграфы

Для каждого $γ > 0$ , когда $n$ достаточно велико, если
$\deg _{r-1}(H)\geq (1/2+\gamma )n$
тогда $H$ гамильтоново и, следовательно, содержит совершенное паросочетание. ^{[ 7 ]}
Если $\deg _{r-1}(H)\geq n/2+3r^{2}{\sqrt {n\log _{2}n}}$
и $n$ достаточно велико, то $H$ допускает идеальное паросочетание. ^{[ 5 ]}
Если $\deg _{r-1}(H)\geq n/r+3r^{2}{\sqrt {n\log _{2}n}},$
тогда $H$ допускает паросочетание, охватывающее все, кроме не более чем $2 r 2$ вершины. ^{[ 5 ]}
Когда n делится на r и достаточно велико, порог равен
$\deg _{r-1}(H)\geq n/2-r+c_{k,n}$
где $c k, n$ — константа, зависящая от четности $n$ и $k$ (все выражения ниже — наилучшие из возможных): ^{[ 8 ]}
- 3 когда $r ⁄ 2$ четный и $n / r$ – нечетное;
- 5 ⁄ 2, когда $r$ нечетно и $(n -1) ⁄ 2$ нечетно;
- 3 ⁄ 2, когда $r$ нечетно и $(n -1) ⁄ 2$ четно;
- 2 иначе.
Когда $n$ не делится на $r$ , достаточная степень близка к $п ⁄ р$ : если $град р -1 (ЧАС) \geq n ⁄ r + O (log(n))$ , то $H$ допускает идеальное паросочетание. Выражение почти наименьшее из возможных: наименьшее возможное — $⌊ n ⁄ r ⌋$ . ^{[ 8 ]}

Другие условия

имеются достаточные условия $Для других значений d$ :

Для всех $d \geq r ⁄ 2$ , порог для $deg d (H)$ близок к: ^{[ 9 ]}
$\left({\frac {1}{2}}+o(1)\right){\binom {n}{r-d}}.$
Для всех $d < r ⁄ 2$ , порог для $deg d (H)$ не превышает: ^{[ 1 ]}
$\left({\frac {r-d}{r}}+o(1)\right){\binom {n-d}{r-d}}$
Если $H$ r $-дольная$ и каждая сторона содержит ровно $n$ вершин, и
$\deg _{d}(H)\geq {\frac {r-d}{r}}n^{r-d}+rn^{r-d-1},$
тогда $H$ содержит паросочетание, охватывающее все вершины, кроме $(d - 1) r$ . ^{[ 1 ]}
Если $n$ достаточно велико и делится на $r$ и
$\deg _{d}(H)\geq {\frac {r-d}{r}}{\binom {n}{r-d}}+r^{r+1}(\ln {n})^{1/2}n^{r-d-1/2},$
тогда $H$ содержит паросочетание, охватывающее все вершины, кроме $(d - 1) r$ . ^{[ 1 ]}

См. также

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

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Хан, Хип; Персона, Юрий; Шахт, Матиас (1 января 2009 г.). «О идеальных паросочетаниях в однородных гиперграфах с большой минимальной степенью вершины». SIAM Journal по дискретной математике . 23 (2): 732–748. дои : 10.1137/080729657 . ISSN 0895-4801 .
^ Хан, Имдадулла (1 января 2013 г.). «Идеальные паросочетания в 3-однородных гиперграфах с большой степенью вершины». SIAM Journal по дискретной математике . 27 (2): 1021–1039. дои : 10.1137/10080796X . ISSN 0895-4801 . S2CID 18434210 .
^ Хан, Имдадулла (1 января 2016 г.). «Совершенные паросочетания в 4-однородных гиперграфах» . Журнал комбинаторной теории, серия B. 116 : 333–366. arXiv : 1101.5675 . дои : 10.1016/j.jctb.2015.09.005 . ISSN 0095-8956 .
^ Перейти обратно: ^а ^б Дайкин, Дэвид Э.; Хэггквист, Роланд (1 февраля 1981 г.). «Степени, дающие независимые ребра в гиперграфе» . Бюллетень Австралийского математического общества . 23 (1): 103–109. дои : 10.1017/S0004972700006924 . ISSN 1755-1633 .
^ Перейти обратно: ^а ^б ^с ^д Кюн, Даниэла; Остус, Дерик (2006). «Сочетания в гиперграфах большой минимальной степени». Журнал теории графов . 51 (4): 269–280. дои : 10.1002/jgt.20139 . ISSN 1097-0118 . S2CID 6769560 .
^ Ахарони, Рон; Георгакопулос, Агелос; Шпруссель, Филипп (1 января 2009 г.). «Совершенные паросочетания в r-частных r-графах » Европейский журнал комбинаторики . 30 (1): 39–42. arXiv : 0911.4008 . дои : 10.1016/j.ejc.2008.02.011 . ISSN 0195-6698 . S2CID 1092170 .
^ Рёдль, Войтех; Семереди, Эндре; Ручинский, Анджей (01 марта 2008 г.). «Приближенная теорема типа Дирака для k-равномерных гиперграфов». Комбинаторика . 28 (2): 229–260. дои : 10.1007/s00493-008-2295-z . ISSN 1439-6912 . S2CID 5799411 .
^ Перейти обратно: ^а ^б Рёдль, Войтех; Ручинский, Анджей; Семереди, Эндре (1 апреля 2009 г.). «Совершенные паросочетания в больших однородных гиперграфах с большой минимальной коллективной степенью» . Журнал комбинаторной теории, серия А. 116 (3): 613–636. дои : 10.1016/j.jcta.2008.10.002 . ISSN 0097-3165 .
^ Пихурко, Олег (01 сентября 2008 г.). «Совершенные паросочетания и K 4 3 -разбиения в гиперграфах большой костепени». Графы и комбинаторика . 24 (4): 391–404. дои : 10.1007/s00373-008-0787-7 . ISSN 0911-0119 . S2CID 29248979 .

[:3-1] Перейти обратно: ^а ^б ^с ^д Хан, Хип; Персона, Юрий; Шахт, Матиас (1 января 2009 г.). «О идеальных паросочетаниях в однородных гиперграфах с большой минимальной степенью вершины». SIAM Journal по дискретной математике . 23 (2): 732–748. дои : 10.1137/080729657 . ISSN 0895-4801 .

[2] Хан, Имдадулла (1 января 2013 г.). «Идеальные паросочетания в 3-однородных гиперграфах с большой степенью вершины». SIAM Journal по дискретной математике . 27 (2): 1021–1039. дои : 10.1137/10080796X . ISSN 0895-4801 . S2CID 18434210 .

[3] Хан, Имдадулла (1 января 2016 г.). «Совершенные паросочетания в 4-однородных гиперграфах» . Журнал комбинаторной теории, серия B. 116 : 333–366. arXiv : 1101.5675 . дои : 10.1016/j.jctb.2015.09.005 . ISSN 0095-8956 .

[:4-4] Перейти обратно: ^а ^б Дайкин, Дэвид Э.; Хэггквист, Роланд (1 февраля 1981 г.). «Степени, дающие независимые ребра в гиперграфе» . Бюллетень Австралийского математического общества . 23 (1): 103–109. дои : 10.1017/S0004972700006924 . ISSN 1755-1633 .

[:0-5] Перейти обратно: ^а ^б ^с ^д Кюн, Даниэла; Остус, Дерик (2006). «Сочетания в гиперграфах большой минимальной степени». Журнал теории графов . 51 (4): 269–280. дои : 10.1002/jgt.20139 . ISSN 1097-0118 . S2CID 6769560 .

[6] Ахарони, Рон; Георгакопулос, Агелос; Шпруссель, Филипп (1 января 2009 г.). «Совершенные паросочетания в r-частных r-графах » Европейский журнал комбинаторики . 30 (1): 39–42. arXiv : 0911.4008 . дои : 10.1016/j.ejc.2008.02.011 . ISSN 0195-6698 . S2CID 1092170 .

[7] Рёдль, Войтех; Семереди, Эндре; Ручинский, Анджей (01 марта 2008 г.). «Приближенная теорема типа Дирака для k-равномерных гиперграфов». Комбинаторика . 28 (2): 229–260. дои : 10.1007/s00493-008-2295-z . ISSN 1439-6912 . S2CID 5799411 .

[:1-8] Перейти обратно: ^а ^б Рёдль, Войтех; Ручинский, Анджей; Семереди, Эндре (1 апреля 2009 г.). «Совершенные паросочетания в больших однородных гиперграфах с большой минимальной коллективной степенью» . Журнал комбинаторной теории, серия А. 116 (3): 613–636. дои : 10.1016/j.jcta.2008.10.002 . ISSN 0097-3165 .

[:2-9] Пихурко, Олег (01 сентября 2008 г.). «Совершенные паросочетания и K 4 3 -разбиения в гиперграфах большой костепени». Графы и комбинаторика . 24 (4): 391–404. дои : 10.1007/s00373-008-0787-7 . ISSN 0911-0119 . S2CID 29248979 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]