Идеальное соответствие в гиперграфах высокой степени - Perfect matching in high-degree hypergraphs

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

Вступление

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

В простом график грамм = (V, E), степень вершины v, часто обозначаемый deg (v) или δ (v), - количество ребер в E рядом с v. Минимальная степень графа, часто обозначаемая deg (грамм) или δ (v), является минимумом deg (v) по всем вершинам v в V.

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

Одно такое условие следует из Теорема Дирака о гамильтоновых циклах. Он говорит, что если deg (грамм) ≥ п/ 2, то граф допускает Гамильтонов цикл; это означает, что он допускает идеальное соответствие. Фактор п/ 2 туго, так как полный двудольный граф на (п/2-1, п/ 2 + 1) вершины имеют степень п/ 2-1, но не допускает идеального соответствия.

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

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

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

Формально для каждого целого числа d ≥ 1, град_d(ЧАС) - минимум deg (U) по всем подмножествам U в V, содержащим ровно d вершины. Таким образом, deg₁(ЧАС) соответствует определению степени простого графа, а именно наименьшей степени отдельной вершины; град₂(ЧАС) - наименьшая степень пары вершин; и Т. Д.

Гиперграф ЧАС = (V, E) называется р-униформа если каждое гиперребро в E содержит точно р вершины V. В р-равномерные графики, соответствующие значения d 1, 2, ..., р-1. На простом графике р=2.

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

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

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

Для сравнения, Теорема Дирака о гамильтоновых циклах говорит, что если ЧАС 2-равномерный (т.е. простой граф) и ${ displaystyle deg _ {1} (H) geq {n-1 choose 1} - {n / 2 choose 1} + 1 = n / 2}$ , тогда ЧАС допускает идеальное соответствие.

Условия на (r-1) -набор степени

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

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

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

Если п≥1000 и ${ displaystyle deg _ {r-1} (H) geq n / 2 + { sqrt {2n log _ {2} n}}}$ , тогда ЧАС имеет идеальное соответствие. Это выражение является минимально возможным с точностью до члена младшего порядка; особенно, п/ 2 недостаточно.^[5]
Если ${ displaystyle deg _ {r-1} (H) geq n / r}$ , тогда ЧАС допускает соответствие, которое охватывает все, кроме р-2 вершины в каждом классе вершин ЧАС. В п/р Фактор по сути является наилучшим из возможных.^[5]
Позволять V₁,...,V_р быть р стороны ЧАС. Если степень каждого (р-1) -набор в V\V₁ строго больше, чем п/ 2, а степень каждого (р-1) -набор в V\V_р по крайней мере п/ 2, то ЧАС допускает идеальное соответствие. ^[6]

В целом р-однородные гиперграфы

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

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

Есть некоторые достаточные условия для других значений d:

Для всех d ≥ р / 2, порог градуса_d(ЧАС) близко к ${ displaystyle left ({ frac {1} {2}} + о (1) right) { binom {n} {r-d}}}$ .^[9]
Для всех d < р / 2, порог градуса_d(ЧАС) не более ${ displaystyle left ({ frac {r-d} {r}} + о (1) right) { binom {n-d} {r-d}}}$ .^[1]
Если H равно р-частный и каждая сторона содержит ровно п вершины и ${ displaystyle deg _ {d} (H) geq { frac {r-d} {r}} n ^ {r-d} + rn ^ {r-d-1}}$ , то H содержит паросочетание, покрывающее все, кроме (d-1)р вершины.^[1]
Если п достаточно велико и делится на р, и ${ Displaystyle deg _ {d} (H) geq { frac {rd} {r}} { binom {n} {rd}} + r ^ {r + 1} ( ln {n}) ^ {1/2} n ^ {rd-1/2}}$ , то H содержит паросочетание, покрывающее все, кроме (d-1)р вершины.^[1]

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

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

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

^ ^а ^б ^c ^d Хан, бедро; Человек, Юрий; Шахт, Матиас (01.01.2009). "О совершенных паросочетаниях в однородных гиперграфах с большой минимальной степенью вершины". Журнал SIAM по дискретной математике. 23 (2): 732–748. Дои:10.1137/080729657. ISSN 0895-4801.
^ Хан, Имдадулла (01.01.2013). «Совершенные сопоставления в 3-однородных гиперграфах с большой степенью вершин». Журнал SIAM по дискретной математике. 27 (2): 1021–1039. Дои:10.1137 / 10080796X. ISSN 0895-4801. S2CID 18434210.
^ Хан, Имдадулла (01.01.2016). «Совершенные сопоставления в 4-однородных гиперграфах». Журнал комбинаторной теории, серия B. 116: 333–366. Дои:10.1016 / j.jctb.2015.09.005. ISSN 0095-8956.
^ ^а ^б Дайкин, Дэвид Э .; Хэггквист, Роланд (1 февраля 1981 г.). «Степени, дающие независимые ребра в гиперграфе». Бюллетень Австралийского математического общества. 23 (1): 103–109. Дои:10.1017 / S0004972700006924. ISSN 1755-1633.
^ ^а ^б ^c ^d Кюн, Даниэла; Остхус, Дерик (2006). «Паросочетания в гиперграфах большой минимальной степени». Журнал теории графов. 51 (4): 269–280. Дои:10.1002 / jgt.20139. ISSN 1097-0118.
^ Ахарони, Рон; Георгакопулос, Агелос; Спрюссель, Филипп (01.01.2009). «Идеальные соответствия в r-разделных r-графах». Европейский журнал комбинаторики. 30 (1): 39–42. arXiv:0911.4008. Дои:10.1016 / j.ejc.2008.02.011. ISSN 0195-6698. S2CID 1092170.
^ Рёдль, Войтех; Семереди, Эндре; Ручиньски, Анджей (01.03.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.09.2008). «Совершенные совпадения и K 4 3-мозаики в гиперграфах большого кода». Графы и комбинаторика. 24 (4): 391–404. Дои:10.1007 / s00373-008-0787-7. ISSN 0911-0119. S2CID 29248979.

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

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

[3] Хан, Имдадулла (01.01.2016). «Совершенные сопоставления в 4-однородных гиперграфах». Журнал комбинаторной теории, серия B. 116: 333–366. Дои: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] а ^б ^c ^d Кюн, Даниэла; Остхус, Дерик (2006). «Паросочетания в гиперграфах большой минимальной степени». Журнал теории графов. 51 (4): 269–280. Дои:10.1002 / jgt.20139. ISSN 1097-0118.

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

[7] Рёдль, Войтех; Семереди, Эндре; Ручиньски, Анджей (01.03.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.09.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]