Соответствие радуги - Rainbow matching

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

Определение

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

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

История

В левом верхнем углу Латинский квадрат, внизу слева относительный собственно п-окраска края. В правом верхнем углу Латинский поперечный а внизу справа относительный соответствие радуги.

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

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

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

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

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

Правильная окраска краев не гарантирует наличия идеального сочетания радуги. Например, рассмотрим график K2,2 - полный двудольный граф на 2 + 2 вершины. Предположим, что ребра (x1, y1) и (x2, y2) окрашены в зеленый цвет, а края (x1, y2) и (x2, y1) окрашены в синий цвет. Это правильный цвет, но есть только два идеальных сочетания, и каждое из них окрашено в один цвет. Возникает вопрос: когда гарантированно существует большое совпадение радуги?

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

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

  • В 1967 г. Х. Дж. Райзер предположил, что когда п является странный, каждая правильная раскраска ребер Kп, п имеет соответствие размера радуги п.[2]
  • В 1975 году С. К. Стейн и Бруальди предположили, что когда п является даже, каждая правильная раскраска ребер Kп, п имеет соответствие размера радуги п-1.[3] (известно, что совпадение размеров радуги п в этом случае может не существовать).

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

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

  • Каждая правильная раскраска ребер Kп, п имеет соответствие радуги размера 2п/3.[4]
  • Каждая правильная раскраска ребер Kп, п имеет соответствие размера радуги п - sqrt (п).[5]
  • Каждая правильная раскраска ребер Kп, п имеет соответствие размера радуги п - 11 журнал22(п).[6]

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

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

  • Димунш и др. ответили на этот вопрос утвердительно и показали, что при правильном раскрашивании ребер г с минимальной степенью d и заказать хотя бы ж(d) = 98δ / 23, существует радужное совпадение размера d в г.[8]
  • Позднее эта оценка была улучшена до ж(d) = 4d - 3 Андраса Гьярфаса и Габора Н. Саркози.[9] Они также показывают, что любой граф с как минимум 2d вершины имеют соответствие размера радуги не менее d-2d2/3. Это самая известная на сегодняшний день оценка.

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

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

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

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

Дриско также показал, что 2пМожет потребоваться -1 совпадение: рассмотрим семью из 2 человекп-2 соответствия, из которых п-1 являются {(x1, y1), (Икс2, y2), ..., (Иксп, yп)} и другие п-1 являются {(x1, y2), (Икс2, y3), ..., (Иксп, y1)}. Тогда самое большое совпадение радуги имеет размер п-1 (например, возьмите по одному ребру каждого из первых п-1 совпадений).

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

В общих двудольных графах

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

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

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

В общих графиках 2п-1 соответствия больше не достаточно. Когда п четно, к примеру Дриско можно добавить соответствие {(x1,Икс2), (y1, y2), (Икс2,Икс3), (y2, y3), ...} и получим семью из 2 человекп-1 совпадений без совпадения радуги.

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

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

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

  • Вместо того, чтобы требовать, чтобы каждый цвет соответствовал размеру п, требование ослаблено: каждый «цвет» может быть произвольным набором ребер, но он должен допускать дробное соответствие размера не менее п.
  • Вместо того, чтобы искать совпадение радуги, мы ищем радуга дробное соответствие - дробное сопоставление, в котором каждое ребро с положительным весом имеет свой цвет.

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

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

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

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

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

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

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

Сопоставление радуги в гиперграфах

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

An r-долевой гиперграф является р-однородный гиперграф, в котором вершины разбиты на р непересекающиеся множества, и каждое гиперребро содержит ровно одну вершину каждого набора (так что двудольный гиперграф - это просто двудольный граф). Позволять п любое положительное целое число. Любая семья rn-р+1 дробное соответствие (= цвета) не менее размера п в р-дольный гиперграф имеет дробное соответствие размера радуги п.[16]:Thm.1.7 В rn-р+1 - наименьший возможный: экстремальный случай - когда п=р-1 - степень простого числа, а все цвета - края усеченного проективная плоскость порядка п. Итак, каждый цвет имеет п2=rn-р+1 ребро и дробное соответствие размера п, но для любого дробного совпадения такого размера требуются все rn-р+1 ребра.[17]

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

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

Заметки

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

Смотрите также: сопоставление в гиперграфах.

Вычисление

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

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

использованная литература

  1. ^ Уэст, Д. (2009), Радужные совпадения
  2. ^ а б Ахарони, Рон; Бергер, Эли; Котлар, Дани; Зив, Ран (2017-01-04). «По догадке Штейна». 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). «Трансверсалии латинских квадратов и их обобщения». Тихоокеанский математический журнал. 59 (2): 567–575. Дои:10.2140 / pjm.1975.59.567. ISSN  0030-8730.
  4. ^ Коксма, Клаас К. (1969-07-01). "Нижняя оценка порядка частичной трансверсали в латинском квадрате". Журнал комбинаторной теории. 7 (1): 94–95. Дои:10.1016 / с0021-9800 (69) 80009-8. ISSN  0021-9800.
  5. ^ Вулбрайт, Дэвид Э (1978-03-01). «Латинский квадрат размера n × n имеет трансверсаль, содержащую не менее n − n различных символов». Журнал комбинаторной теории, серия А. 24 (2): 235–237. Дои:10.1016/0097-3165(78)90009-2. ISSN  0097-3165.
  6. ^ Хатами, Пуйя; Шор, Питер В. (2008-10-01). «Нижняя оценка длины частичной трансверсали в латинском квадрате». Журнал комбинаторной теории, серия А. 115 (7): 1103–1113. Дои:10.1016 / j.jcta.2008.01.002. ISSN  0097-3165.
  7. ^ Ван, Гуанхуэй (2009), «Соответствие радуги в правильно раскрашенных краях графов», Электронный журнал комбинаторики, 18 (1): 162
  8. ^ Димунш, Дженнифер; Феррара, Майкл; Ло, Аллан; Моффатт, Кейси; Пфендер, Флориан; Венгер, Пол С. (2012), «Радужные соответствия размера δ (G) в графах с правильной окраской ребер», Электронный журнал комбинаторики, 19 (2): 52, Дои:10.37236/2443, S2CID  119177198
  9. ^ Гьярфас, Андраш; Саркози, Габор Н. (2012). «Радужные совпадения и частичные трансверсалии латинских квадратов». arXiv:1208.5670 [CO математика. CO ].
  10. ^ Дриско, Артур А. (1998-11-01). «Трансверсали в рядных латинских прямоугольниках». Журнал комбинаторной теории, серия А. 84 (2): 181–195. Дои:10.1006 / jcta.1998.2894. ISSN  0097-3165.
  11. ^ Алон, Нога (2011). «Разноцветные сопоставления в гиперграфах». Московский журнал комбинаторной теории чисел.. 1: 3–10.
  12. ^ Флорес, Карлос; Ордас, Оскар (1996-05-01). «О теореме Эрдеша-Гинзбурга-Зива». Дискретная математика. 152 (1–3): 321–324. Дои:10.1016 / 0012-365x (94) 00328-г. ISSN  0012-365X.
  13. ^ а б Ахарони, Рон; Бергер, Эли (25 сентября 2009 г.). "Соответствие радуги в $ r $ -частных $ r $ -графах". Электронный журнал комбинаторики. 16 (1). Дои:10.37236/208. ISSN  1077-8926.
  14. ^ Ахарони, Рон; Котлар, Дани; Зив, Ран (2018-01-01). «Единственность крайних случаев в теоремах Дриско и Эрдеша – Гинзбурга – Зива». Европейский журнал комбинаторики. 67: 222–229. Дои:10.1016 / j.ejc.2017.08.008. ISSN  0195-6698. S2CID  38268762.
  15. ^ Ахарони, Рон; Бергер, Эли; Чудновский, Мария; Ховард, Дэвид; Сеймур, Пол (2019-06-01). «Большие совпадения радуги в общих графиках». Европейский журнал комбинаторики. 79: 222–227. arXiv:1611.03648. Дои:10.1016 / j.ejc.2019.01.012. ISSN  0195-6698. S2CID  42126880.
  16. ^ а б c d Ахарони, Рон; Хольцман, Рон; Цзян, Зилинь (2019-10-29). «Радужные дробные совпадения». Комбинаторика. 39 (6): 1191–1202. arXiv:1805.09732. Дои:10.1007 / s00493-019-4019-у. ISSN  0209-9683. S2CID  119173114.
  17. ^ Фюреди, Золтан (1 мая 1989 г.). «Покрытие всего графа разбиениями». Дискретная математика. 75 (1–3): 217–226. Дои:10.1016 / 0012-365x (89) 90088-5. ISSN  0012-365X.
  18. ^ Гарей, М.; Джонсон, Д.С. (1979). Виктор Клее (ред.). Компьютеры и непреодолимость: руководство по теории NP-полноты. Серия книг по математическим наукам. Сан-Франциско, Калифорния: W.H. Freeman and Co., стр.х + 338. ISBN  0-7167-1045-5. Г-Н  0519066.CS1 maint: ref = harv (ссылка на сайт)