stringtranslate.com

Радужное соответствие

В математической дисциплине теории графов радужное паросочетание в графе с раскрашенными рёбрами — это паросочетание , в котором все рёбра имеют разные цвета.

Определение

Для графа G = ( V , E ) с раскрашенными ребрами радужное паросочетание M в G представляет собой набор попарно несмежных ребер, то есть никакие два ребра не имеют общей вершины, так что все ребра в наборе имеют разные цвета.

Максимальное радужное паросочетание — это радужное паросочетание, которое содержит наибольшее возможное количество ребер.

История

В верхнем левом углу латинский квадрат , в нижнем левом углу относительная правильная раскраска n - рёбер . В верхнем правом углу латинская трансверсаль , а в нижнем правом углу относительное радужное соответствие .

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

Обозначим через K n , n полный двудольный граф на n + n вершинах. Каждая правильная n - рёберная раскраска графа K n , n соответствует латинскому квадрату порядка n . Тогда радужное паросочетание соответствует трансверсали латинского квадрата, что означает выборку из n позиций, по одной в каждой строке и каждом столбце, содержащих различные записи.

Эта связь между трансверсалями латинских квадратов и радужными паросочетаниями в K n , n вызвала дополнительный интерес к изучению радужных паросочетаний в графах без треугольников . [1]

Существование, когда каждое ребро имеет один цвет

Раскраска ребер называется правильной , если каждое ребро имеет один цвет и каждые два ребра одного цвета не имеют общих вершин.

Правильная раскраска ребер не гарантирует существование идеального радужного паросочетания. Например, рассмотрим граф K 2,2 : полный двудольный граф с 2+2 вершинами. Предположим, что ребра ( x 1 , y 1 ) и ( x 2 , y 2 ) окрашены в зеленый цвет, а ребра ( x 1 , y 2 ) и ( x 2 , y 1 ) — в синий. Это правильная раскраска, но существует только два идеальных паросочетания, и каждое из них окрашено в один цвет. Это вызывает вопрос: когда гарантированно существует большое радужное паросочетание?

Границы, зависящие только от количества вершин

Большая часть исследований по этому вопросу была опубликована с использованием терминологии латинских трансверсалей в латинских квадратах . Переведено на терминологию сопоставления радуги:

Более общая гипотеза Штейна заключается в том, что радужное паросочетание размера n – 1 существует не только для правильной раскраски ребер, но и для любой раскраски, в которой каждый цвет появляется ровно на n ребрах. [2]

Были доказаны некоторые более слабые версии этих гипотез:

Границы в зависимости от минимальной степени

Ван спросил, существует ли функция f ( d ) такая, что каждый правильно раскрашенный граф G с минимальной степенью d и по крайней мере f ( d ) вершинами должен иметь радужное паросочетание размера d . [9] Очевидно, что необходимо по крайней мере 2 d вершин, но сколько их достаточно?

Существование, когда одно и то же ребро может иметь разные цвета

Предположим, что каждое ребро может иметь несколько разных цветов, в то время как каждые два ребра одного цвета по-прежнему не должны иметь общих вершин. Другими словами, каждый цвет является соответствием . Сколько цветов необходимо, чтобы гарантировать существование радужного соответствия?

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

Дриско [12] изучал этот вопрос, используя терминологию латинских прямоугольников . Он доказал, что для любого n ≤ k в полном двудольном графе K n , k любое семейство из 2 n – 1 паросочетаний (=цветов) размера n имеет совершенное радужное паросочетание (размера n ). Он применил эту теорему к вопросам о групповых действиях и разностных множествах .

Дриско также показал, что может потребоваться 2 n – 1 сопоставлений: рассмотрим семейство из 2 n – 2 сопоставлений, из которых n – 1 — это {( x 1 , y 1 ), ( x 2 , y 2 ), ..., ( x n , y n )}, а остальные n – 1 — это {( x 1 , y 2 ), ( x 2 , y 3 ), …, ( x n , y 1 ) }. Тогда наибольшее радужное сопоставление имеет размер n – 1 (например, взять по одному ребру из каждого из первых n – 1 сопоставлений).

Алон [13] показал, что теорема Дриско подразумевает более старый результат [14] из теории аддитивных чисел .

В общем случае двудольные графы

Ахарони и Бергер [15] обобщили теорему Дриско на любой двудольный граф, а именно: любое семейство из 2 n – 1 паросочетаний размера n в двудольном графе имеет радужное паросочетание размера n .

Ахарони, Котлар и Зив [16] показали, что экстремальный пример Дриско уникален в любом двудольном графе.

В общих графиках

В общих графах 2 n – 1 сопоставлений уже недостаточно. Когда n четное, можно добавить к примеру Дриско сопоставление { ( x 1 , x 2 ), ( y 1 , y 2 ), ( x 2 , x 3 ), ( y 2 , y 3 ), … } и получить семейство из 2 n – 1 сопоставлений без радужных сопоставлений.

Ахарони, Бергер, Чудновский, Говард и Сеймур [17] доказали, что в общем графе всегда достаточно 3 n – 2 сопоставлений (=цветов). Неизвестно, является ли это точным: в настоящее время наилучшая нижняя граница для четных n равна 2 n , а для нечетных n равна 2 n – 1 . [18]

Радужные дробные паросочетания

Дробное сопоставление — это набор ребер с неотрицательным весом, назначенным каждому ребру, так что сумма весов, смежных с каждой вершиной, не превышает 1. Размер дробного сопоставления — это сумма весов всех ребер. Это обобщение сопоставления, и его можно использовать для обобщения как сопоставления цветов, так и сопоставления радуги:

Известно, что в двудольном графе максимальный размер дробного паросочетания равен максимальному размеру паросочетания. Поэтому теорема Ахарони и Бергера [15] эквивалентна следующему. Пусть n — любое положительное целое число. Для любого семейства из 2 n – 1 дробных паросочетаний (=цветов) размера n в двудольном графе существует радужное дробное паросочетание размера n .

Ахарони, Хольцман и Цзян распространяют эту теорему на произвольные графы следующим образом. Пусть n — любое положительное целое или полуцелое число. Любое семейство из 2 n дробных-сопоставлений (=цветов) размера не менее n в произвольном графе имеет радужное-дробное-сопоставление размера n . [18] : Теорема  1.5 2 n — наименьшее возможное число для дробных сопоставлений в произвольных графах: экстремальный случай строится с использованием цикла нечетной длины.

Частичное доказательство

Для случая совершенных дробных паросочетаний обе приведенные выше теоремы могут быть выведены из красочной теоремы Каратеодори .

Для каждого ребра e в E пусть 1 e будет вектором размера | V | , где для каждой вершины v в V элемент v в 1 e равен 1, если e смежна с v , и 0 в противном случае (так что каждый вектор 1 e имеет 2 единицы и | V | -2 нуля). Каждое дробное паросочетание соответствует конической комбинации ребер, в которой каждый элемент не превышает 1. Коническая комбинация, в которой каждый элемент равен ровно 1, соответствует совершенному дробному паросочетанию. Другими словами, набор F ребер допускает совершенное дробное паросочетание, если и только если 1 v (вектор из | V | единиц) содержится в конической оболочке векторов 1 e для e в F .

Рассмотрим граф с 2 n вершинами и предположим, что имеется 2 n подмножеств ребер, каждое из которых допускает совершенное дробное паросочетание (размера n ). Это означает, что вектор 1 v находится в конической оболочке каждого из этих n подмножеств. По красочной теореме Каратеодори существует выборка из 2 n ребер, по одному из каждого подмножества, что их коническая оболочка содержит 1 v . Это соответствует радужному совершенному дробному паросочетанию. Выражение 2 n является размерностью векторов 1 e - каждый вектор имеет 2 n элементов.

Теперь предположим, что граф двудольный. В двудольном графе на векторы 1 e накладывается ограничение : сумма элементов, соответствующих каждой части графа, должна быть равна 1. Следовательно, векторы 1 e находятся в (2 n – 1) -мерном пространстве. Следовательно, тот же аргумент, что и выше, справедлив, когда имеется только 2 n – 1 подмножеств ребер.

Радужное соответствие в гиперграфах

r -однородный гиперграф — это набор гиперребер, каждое из которых содержит ровно r вершин (поэтому 2-однородный гиперграф — это просто граф без петель). Ахарони, Хольцман и Цзян расширяют свою теорему на такие гиперграфы следующим образом. Пусть n — любое положительное рациональное число. Любое семейство ⌈ r ⋅ n ⌉ дробных паросочетаний (=цветов) размера не менее n в r -однородном гиперграфе имеет радужное дробное паросочетание размера n . [18] : Теорема 1.6  ⌈ r ⋅ n ⌉ является наименьшим возможным, когда n — целое число.

r -дольный гиперграф — это r -однородный гиперграф, в котором вершины разделены на r непересекающихся множеств, и каждое гиперребро содержит ровно одну вершину из каждого множества (поэтому 2-дольный гиперграф — это просто двудольный граф). Пусть n — любое положительное целое число. Любое семейство из rn – r + 1 дробных сопоставлений (=цветов) размера не менее n в r -дольном гиперграфе имеет радужное дробное сопоставление размера n . [18] : Теор.1.7 rn – r + 1 является наименьшим возможным :  экстремальный случай — когда n = r – 1 является степенью простого числа , а все цвета являются ребрами усеченной проективной плоскости порядка n . Таким образом, каждый цвет имеет n 2 = rn – r + 1 ребер и дробное сопоставление размера n , но любое дробное сопоставление такого размера требует всех rn – r + 1 ребер. [19]

Частичное доказательство

Для случая совершенных дробных паросочетаний обе приведенные выше теоремы могут быть выведены из красочной теоремы Каратеодори в предыдущем разделе. Для общего r -однородного гиперграфа (допускающего совершенное паросочетание размера n ) векторы 1 e живут в ( rn ) -мерном пространстве. Для r -однородного r -дольного гиперграфа ограничения r -дольности подразумевают, что векторы 1 e живут в ( rn – r + 1) -мерном пространстве.

Примечания

Приведенные выше результаты справедливы только для радужных дробных паросочетаний. Напротив, случай радужных интегральных паросочетаний в r -однородных гиперграфах изучен гораздо меньше. Количество требуемых паросочетаний для радужного паросочетания размера n растет по крайней мере экспоненциально с n .

Вычисление

Гари и Джонсон показали, что вычисление максимального радужного паросочетания является NP-полной задачей даже для двудольных графов с раскрашенными рёбрами . [20]

Приложения

Радужные соответствия применялись для решения задач упаковки . [21]

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

Ссылки

  1. ^ Уэст, ДБ (2009), Rainbow Matchings
  2. ^ аб Ахарони, Рон; Бергер, Эли; Котлар, Дэни; Зив, Ран (04 января 2017 г.). «О догадке Штейна». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 87 (2): 203–211. дои : 10.1007/s12188-016-0160-3. ISSN  0025-5858. S2CID  119139740.
  3. ^ Стайн, Шерман (1975-08-01). «Трансверсали латинских квадратов и их обобщения». Pacific Journal of Mathematics . 59 (2): 567–575. doi : 10.2140/pjm.1975.59.567 . ISSN  0030-8730.
  4. ^ Коксма, Клаас К. (1969-07-01). «Нижняя граница порядка частичной трансверсали в латинском квадрате». Журнал комбинаторной теории . 7 (1): 94–95. doi : 10.1016/s0021-9800(69)80009-8 . ISSN  0021-9800.
  5. ^ Вулбрайт, Дэвид Э. (1978-03-01). «Латинский квадрат n × n имеет трансверсаль с по крайней мере n−n различными символами». Журнал комбинаторной теории, Серия A. 24 ( 2): 235–237. doi : 10.1016/0097-3165(78)90009-2 . ISSN  0097-3165.
  6. ^ Хатами, Пуйя; Шор, Питер В. (2008-10-01). «Нижняя граница длины частичной трансверсали в латинском квадрате». Журнал комбинаторной теории, Серия A. 115 ( 7): 1103–1113. doi : 10.1016/j.jcta.2008.01.002 . ISSN  0097-3165.
  7. ^ Киваш, Питер; Покровский, Алексей; Судаков, Бенни; Епремян, Лиана (2022-04-15). «Новые границы для гипотезы Райзера и связанные с ней проблемы». Труды Американского математического общества, серия B. 9 ( 8): 288–321. arXiv : 2005.00526 . doi : 10.1090/btran/92 . ISSN  2330-0000.
  8. ^ Монтгомери, Ричард (2023). «Доказательство гипотезы Райзера-Бруальди-Стейна для больших четных n ». arXiv : 2310.19779 [math.CO].
  9. ^ Ван, Гуанхуэй (2009), «Радужные соответствия в графах с правильной раскраской краев», Электронный журнал комбинаторики , 18 (1): 162
  10. ^ Димунш, Дженнифер; Феррара, Майкл; Ло, Аллан; Моффатт, Кейси; Пфендер, Флориан; Венгер, Пол С. (2012), «Радужные соответствия размера δ(G) в графах с правильной раскраской рёбер», The Electronic Journal of Combinatorics , 19 (2): 52, arXiv : 1108.2521 , doi : 10.37236/2443 , S2CID  119177198
  11. ^ Gyarfas, Andras; Sarkozy, Gabor N. (2012). «Радужные соответствия и частичные трансверсали латинских квадратов». arXiv : 1208.5670 [CO math. CO].
  12. ^ Дриско, Артур А. (1 ноября 1998 г.). «Трансверсали в рядно-латинских прямоугольниках». Журнал комбинаторной теории, серия A. 84 ( 2): 181–195. doi : 10.1006/jcta.1998.2894 . ISSN  0097-3165.
  13. ^ Алон, Нога (2011). «Многоцветные паросочетания в гиперграфах». Московский журнал комбинаторики и теории чисел . 1 : 3–10.
  14. ^ Флорес, Карлос; Ордас, Оскар (1996-05-01). «О теореме Эрдёша-Гинзбурга-Зива». Дискретная математика . 152 (1–3): 321–324. doi : 10.1016/0012-365x(94)00328-g . ISSN  0012-365X.
  15. ^ ab Ахарони, Рон; Бергер, Эли (2009-09-25). "Радужное соответствие в $r$-дольных $r$-графах". Электронный журнал комбинаторики . 16 (1). doi : 10.37236/208 . ISSN  1077-8926.
  16. ^ Ахарони, Рон; Котлар, Дэни; Зив, Ран (01 января 2018 г.). «Единственность крайних случаев в теоремах Дриско и Эрдеша – Гинзбурга – Зива». Европейский журнал комбинаторики . 67 : 222–229. дои : 10.1016/j.ejc.2017.08.008 . ISSN  0195-6698. S2CID  38268762.
  17. ^ Ахарони, Рон; Бергер, Эли; Чудновский, Мария; Ховард, Дэвид; Сеймур, Пол (01 июня 2019 г.). «Большие радужные паросочетания в общих графах». Европейский журнал комбинаторики . 79 : 222–227. arXiv : 1611.03648 . doi :10.1016/j.ejc.2019.01.012. ISSN  0195-6698. S2CID  42126880.
  18. ^ abcd Ахарони, Рон; Хольцман, Рон; Цзян, Цзилинь (29 октября 2019 г.). «Радужные дробные соответствия». Комбинаторика . 39 (6): 1191–1202. arXiv : 1805.09732 . doi : 10.1007/s00493-019-4019-y. ISSN  0209-9683. S2CID  119173114.
  19. ^ Фюреди, Золтан (1989-05-01). «Покрытие полного графа разбиениями». Дискретная математика . 75 (1–3): 217–226. doi : 10.1016/0012-365x(89)90088-5 . ISSN  0012-365X.
  20. ^ Garey, M. R .; Johnson, D. S. (1979). Victor Klee (ред.). Computers and Intractability: A Guide to the Theory of NP-Completeness . Серия книг по математическим наукам. Сан-Франциско, Калифорния: W. H. Freeman and Co. стр. x+338. ISBN 0-7167-1045-5. МР  0519066.
  21. ^ Баннах, Макс; Берндт, Себастьян; Маак, Мартен; Мних, Маттиас; Лассота, Александра; Рау, Малин; Скамбат, Мальте (2020-07-06). «Решение задач упаковки с несколькими мелкими предметами с использованием радужных совпадений». arXiv : 2007.02660 [cs.DS].