В теории графов , совершенное паросочетание в высокой степени гиперграфов является исследование проспект пытается найти достаточные условия для существования паросочетания в гиперграфе , основываясь только на степени вершин или подмножеств из них.
Вступление
Степени и совпадения в графиках
В простом графе G = ( V , E ) степень вершины v , часто обозначаемая через deg ( v ) или δ ( v ), - это количество ребер в E, смежных с v . Минимальная степень графа, часто обозначают через & deg ; ( G ) или б ( об ), является минимумом град ( v ) по всем вершинам V в V .
Соответствия в графе представляет собой набор ребер таким образом, что каждая вершина смежна не более одного ребра; идеальное соответствие является соответствие , в котором каждая вершина смежна с одного края. Идеальное соответствие не всегда существует, поэтому интересно найти достаточные условия, гарантирующие его существование.
Одно такое условие следует из теоремы Дирака о гамильтоновых циклах . Он говорит, что если deg ( G ) ≥ n / 2, то граф допускает гамильтонов цикл ; это означает, что он допускает идеальное соответствие. Фактор n / 2 является точным, так как полный двудольный граф на ( n / 2-1, n / 2 + 1) вершинах имеет степень n / 2-1, но не допускает идеального паросочетания.
Описанные ниже результаты направлены на распространение этих результатов с графиков на гиперграфы .
Степени в гиперграфах
В гиперграфа H = (V, E), каждое ребро Е может содержать более двух вершин V . Степень вершины v в V , как и прежде, равна количеству ребер в E , содержащих v . Но в гиперграфе можно также учитывать степень подмножеств вершин: дано подмножество U в V , град ( U ) есть число ребер в E , которые содержат все вершины U . Таким образом, степень гиперграфа может быть определена по-разному в зависимости от размера подмножеств, степень которых рассматривается.
Формально для любого целого числа d ≥ 1 deg d ( H ) является минимумом deg ( U ) по всем подмножествам U в V, содержащим ровно d вершин. Таким образом, deg 1 ( H ) соответствует определению степени простого графа, а именно наименьшей степени отдельной вершины; deg 2 ( H ) - наименьшая степень пары вершин; и т.п.
Гиперграф Н = ( V , E ) называется г -равномерная , если каждый гиперребро в Е содержит ровно г вершины V . В r- однородных графах соответствующие значения d равны 1, 2, ..., r -1. В простом графе r = 2.
Условия на 1-вершинную степень
Несколько авторов доказали достаточные условия для случая d = 1, т. Е. Условия на наименьшую степень одиночной вершины.
- Если H 3-равномерный гиперграф на n вершинах, n делится на 3 и, то H содержит идеальное паросочетание. [1]
- Если H 3-равномерный гиперграф на n вершинах, n делится на 3 и, то H содержит идеальное соответствие - соответствие размера k . Это лучший результат. [2]
- Если H - 4-равномерный гиперграф с n вершинами, n делится на 4 и, то H содержит идеальное сопоставление - сопоставление размера k . Это лучший результат. [3]
- Если Н является г -равномерным, п является кратным р , и, то H содержит паросочетание размером не менее k +1. В частности, установка k = n / r -1 дает, что если, то H содержит идеальное паросочетание. [4]
- Если Н является г -равномерной и т -дольным, каждая сторона содержит ровно п вершин, и, то H содержит паросочетание размером не менее k +1. В частности, установка k = n -1 дает, что если, то H содержит идеальное паросочетание. [4]
Для сравнения, теорема Дирака о гамильтоновых циклах гласит, что если H 2-однороден (т. Е. Простой граф) и, то H допускает совершенное паросочетание.
Условия на (r-1) -набор степени
Несколько авторов доказали достаточные условия для случая d = r -1, т. Е. Условия на наименьшую степень множеств из r -1 вершин в r -однородных гиперграфах с n вершинами.
В r -дольных r -однородных гиперграфах
Следующие результаты относятся к r -раздельным гиперграфам, имеющим ровно n вершин на каждой стороне (всего rn вершин):
- Если n ≥1000 и, то H имеет идеальное паросочетание. Это выражение является наименьшим возможным с точностью до члена младшего порядка; в частности, n / 2 недостаточно. [5]
- Если , То Н допускает согласование , который охватывает все , но в большинстве г -2 вершин в каждом классе вершин H . П / г фактором является по существу наилучшим возможным. [5]
- Пусть V 1 , ..., V г быть г стороны Н . Если степень каждого ( r -1) -набора в V \ V 1 строго больше, чем n / 2, а степень каждого ( r -1) -набора в V \ V r не меньше n / 2, то H допускает идеальное совпадение. [6]
В общем случае r -однородные гиперграфы
- Для любого γ> 0, когда n достаточно велико, еслитогда H гамильтонова и, следовательно, содержит идеальное паросочетание. [7]
- Если n достаточно велико и, то H допускает совершенное паросочетание. [5]
- Если , то H допускает паросочетание, которое покрывает все вершины, кроме 2 r 2 . [5]
- Когда n делится на r и достаточно велико, порог равен, где 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 , достаточная степень близка к n / r: еслитогда H допускает идеальное совпадение. Выражение почти наименьшее возможное: наименьшее возможное. [8]
Другие условия
Для других значений d есть несколько достаточных условий :
- Для всех d ≥ r / 2 порог deg d ( H ) близок к. [9]
- Для всех d < r / 2 порог deg d ( H ) не превосходит. [1]
- Если H r -раздельная и каждая сторона содержит ровно n вершин, и, то H содержит паросочетание, покрывающее все вершины, кроме ( d -1) r . [1]
- Если n достаточно велико и делится на r , и, то H содержит паросочетание, покрывающее все вершины, кроме ( d -1) r . [1]
Смотрите также
- Теоремы типа Холла для гиперграфов - перечисляются другие достаточные условия существования идеальных паросочетаний в гиперграфах, аналогичные теореме Холла о браке.
Рекомендации
- ^ a b c d Хан, Бедро; Человек, Юрий; Шахт, Матиас (01.01.2009). «О совершенных паросочетаниях в однородных гиперграфах с большой минимальной степенью вершины». Журнал СИАМ по дискретной математике . 23 (2): 732–748. DOI : 10.1137 / 080729657 . ISSN 0895-4801 .
- ^ Хан, Имдадулла (01.01.2013). «Совершенные сопоставления в 3-однородных гиперграфах с большой степенью вершин». Журнал СИАМ по дискретной математике . 27 (2): 1021–1039. DOI : 10.1137 / 10080796X . ISSN 0895-4801 . S2CID 18434210 .
- ^ Хан, Имдадулла (01.01.2016). «Совершенные сопоставления в 4-однородных гиперграфах» . Журнал комбинаторной теории, серии B . 116 : 333–366. DOI : 10.1016 / j.jctb.2015.09.005 . ISSN 0095-8956 .
- ^ а б Дайкин, Дэвид Э .; Хэггквист, Роланд (1 февраля 1981 г.). «Степени, дающие независимые ребра в гиперграфе» . Бюллетень Австралийского математического общества . 23 (1): 103–109. DOI : 10.1017 / S0004972700006924 . ISSN 1755-1633 .
- ^ а б в г Кюн, Даниэла; Остхус, Дерик (2006). «Паросочетания в гиперграфах большой минимальной степени». Журнал теории графов . 51 (4): 269–280. DOI : 10.1002 / jgt.20139 . ISSN 1097-0118 .
- ^ Ахарони, Рон; Георгакопулос, Агелос; Спрюссель, Филипп (01.01.2009). «Совершенные сопоставления в r-раздельных r-графах» . Европейский журнал комбинаторики . 30 (1): 39–42. arXiv : 0911.4008 . DOI : 10.1016 / j.ejc.2008.02.011 . ISSN 0195-6698 . S2CID 1092170 .
- ^ Рёдль, Войтех; Семереди, Эндре; Ручинский, Анджей (01.03.2008). «Приближенная теорема типа Дирака для k-равномерных гиперграфов». Combinatorica . 28 (2): 229–260. DOI : 10.1007 / s00493-008-2295-z . ISSN 1439-6912 . S2CID 5799411 .
- ^ а б Рёдль, Войтех; Ручинский, Анджей; Семереди, Эндре (1 апреля 2009 г.). «Совершенные сопоставления в больших однородных гиперграфах с большой минимальной коллективной степенью» . Журнал комбинаторной теории, Серия А . 116 (3): 613–636. DOI : 10.1016 / j.jcta.2008.10.002 . ISSN 0097-3165 .
- ^ Пихурко, Олег (01.09.2008). «Совершенные совпадения и K 4 3-мозаики в гиперграфах большого кодового дерева». Графы и комбинаторика . 24 (4): 391–404. DOI : 10.1007 / s00373-008-0787-7 . ISSN 0911-0119 . S2CID 29248979 .