Независимый от радуги набор

В теории графов ( независимое от радуги множество ISR ) — это независимое множество в графе , в котором каждая вершина имеет свой цвет .

Формально, пусть $G = (V, E)$ — граф, и предположим, что множество вершин $на$ m V разделено подмножеств $V$ 1 $, \dots, V m$ , называемых «цветами». Множество $U$ вершин называется независимым от радуги множеством, если оно удовлетворяет обоим следующим условиям: ^[1]

Это независимое множество – каждые две вершины в $U$ несмежны (между ними нет ребра);
Это радужное множество : $U$ не более одной вершины каждого цвета $Vi содержит$ .

Другими терминами, используемыми в литературе, являются независимый набор представителей , ^[2] независимая поперечная , ^[3] и независимая система представителей . ^[4]

В качестве примера рассмотрим факультет с $m$ кафедрами, где некоторые преподаватели не любят друг друга. Декан хочет создать комитет из $m$ членов, по одному на факультет, но без пары членов, которые не любят друг друга. Эту задачу можно представить как поиск ИСР в графе, в котором узлами являются преподаватели, ребра описывают отношения «неприязни», а подмножества $V 1, \dots, V m$ – кафедры. ^[3]

Варианты

Для удобства предполагается, что множества $V 1, \dots, V m$ попарно непересекающиеся. В общем, множества могут пересекаться, но этот случай можно легко свести к случаю непересекающихся множеств: для каждой вершины $сформируйте$ копию $x$ для каждого $i,$ такого, что $Vi x$ содержит $x$ . В полученном графе соедините все копии $x$ друг с другом. В новом графе $V i$ не пересекаются, и каждый ISR соответствует ISR в исходном графе. ^[4]

ISR обобщает концепцию системы отдельных представителей (SDR, также известную как трансверсальная ). Каждая трансверсаль представляет собой ISR, в котором в базовом графе соединены все и только копии одной и той же вершины из разных наборов.

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

Существуют различные достаточные условия существования ИСР.

Условие, основанное на степени вершины

когда кафедры $VI Интуитивно понятно, что$ больше и между преподавателями меньше конфликтов, вероятность существования ISR возрастает. Условие «меньше конфликтов» представлено степенью вершины графа. Это формализуется следующей теоремой: ^[5]^{: Thm.2}

Если степень каждой вершины в $G$ не превышает $d$ , а размер каждого набора цветов не менее $2 d$ , то $G$ имеет ISR.

2d $k без$ лучше всего: есть граф со степенью вершины $и$ размера $2d цветами - 1$ ISR. ^[6] Но существует более точная версия, в которой оценка зависит как от $d,$ так и от $m$ . ^[7]

Условие, основанное на доминирующих множествах

Ниже, учитывая подмножество $S$ цветов (подмножество ${V 1, ..., V m}$ ), мы обозначаем $U S$ объединение всех подмножеств в $S$ (все вершины, цвет которых является одним из цветов в $S$ ) , а через $GS —$ подграф $G,$ индуцированный $US S$ . ^[8] Следующая теорема описывает структуру графов, которые не имеют ISR, но минимальны по ребру , в том смысле, что всякий раз, когда из них удаляется какое-либо ребро, оставшийся граф имеет ISR.

Если $G$ не имеет ISR, но для каждого ребра $в$ E $Ge$ имеет $V$ ISR, то для каждого ребра $e = (x, y)$ в $E$ существует подмножество $S$ цветов ${e 1, \dots, V m} ,$ набор $Z$ ребер $GS и$ , такие что:
вершины $x$ и $y$ находятся в $US;$ Обе
Ребро $e = (x, y)$ находится в $Z$ ;
Множество вершин, смежных с $Z,$ доминирует $GS над$ ;
$| Я | \leq | С | - 1$ ;
$Z$ является паросочетанием : никакие два его ребра не примыкают к одной и той же вершине.

Состояние холлового типа

Ниже, учитывая подмножество $S$ цветов (подмножество ${V 1, \dots, V m}$ независимое множество $I S$ из $GS если$ называется специальным для $S,$ для каждого независимого подмножества $J$ вершин $GS) ,$ размера в большинство $| С | - 1$ , существует такой $v$ в $I S$ , что $J \cup {v}$ также независим. Образно говоря, $I S$ — это команда «нейтральных членов» набора $S$ отделов, которая может дополнить любой достаточно малый набор неконфликтующих членов, чтобы создать такой набор большего размера. Следующая теорема аналогична теореме Холла о браке : ^[9]

Если для каждого подмножества S цветов граф $содержит GS$ независимый набор $IS,$ специальный для $S$ , то $G$ имеет ISR.

Идея доказательства . Теорема доказывается с помощью леммы Спернера . ^[3]^{: Thm.4.2} Стандартному симплексу с $m$ концами присваивается триангуляция с некоторыми особыми свойствами. Каждая конечная точка $i$ симплекса связана с набором цветов $V i$ , каждая грань ${i 1, \dots, i k}$ симплекса связана с набором $S = {V i 1, \dots, V ik}$ цветов. точка $x$ триангуляции помечена вершиной $g (x)$ из $G$ такой, что: (a) Для каждой точки $x$ на грани $S$ Каждая $g (x)$ является элементом $IS S.$ специального независимого $множества$ – (b) Если точки $x$ и $y$ смежны в 1-скелете триангуляции, то $(x) и$ g $(y) не$ смежны в $G.$ g По лемме Спернера существует субсимплекс, в котором для каждой точки $g$ x $(x) принадлежит$ разному набору цветов; набор этих $g (x)$ является ISR.

Из приведенной выше теоремы следует условие брака Холла. Чтобы убедиться в этом, полезно сформулировать теорему для частного случая, когда $G$ является линейным графом некоторого другого графа $H$ ; что каждая вершина $G$ является ребром $H$ , а каждое независимое множество $G$ является паросочетанием в $H.$ это означает , Раскраска вершин $G$ соответствует раскраске ребер $H$ , а независимый от радуги набор в $G$ соответствует сопоставлению радуги в $H$ . Паросочетание $IS,$ в $HS является$ специальным для $S$ если для каждого паросочетания $J$ в $HS более$ размера не $| С | - 1$ , существует ребро $e$ в $I S$ такое, что $J \cup {e}$ паросочетанием в $HS по-прежнему является$ .

Пусть $H$ — граф с раскраской ребер. Если для каждого подмножества $S$ цветов граф $содержит HS$ паросочетание $MS,$ специальное для $S$ , то $H$ имеет радужное сопоставление.

Пусть $H = (X + Y, E)$ — двудольный граф, удовлетворяющий условию Холла. Для каждой вершины $i$ из $X$ назначьте уникальный цвет $всем Vi$ ребрам $H,$ смежным с $i$ . Для каждого подмножества $S$ цветов условие Холла означает, что $S$ имеет по крайней мере $| С |$ соседей в $Y$ , и, следовательно, существует не менее $| С |$ ребра $H,$ смежные с различными вершинами $Y$ . Пусть $I S$ — набор $| С |$ такие края. Для любого совпадения $J$ размера не более $| С | - 1$ в $H$ , некоторый элемент $e$ из $I S$ имеет другую конечную точку в $Y,$ чем все элементы $J$ , и, таким образом, $\cup {e}$ также является паросочетанием, поэтому $I S$ является специальным для $S.$ J Из приведенной выше теоремы следует, что $H$ имеет радужное паросочетание $M R$ . По определению цветов $MR —$ идеальное паросочетание в $H$ .

Другим следствием приведенной выше теоремы является следующее условие, которое включает в себя как степень вершины, так и длину цикла: ^[3]^{: Thm.4.3}

Если степень каждой вершины в $G$ не превышает 2, длина каждого цикла $G$ делится на 3, а размер каждого набора цветов не менее 3, то $G$ имеет ISR.

Доказательство. Для каждого подмножества $S$ цветов граф $содержит GS$ не менее $3| С |$ вершин и представляет собой объединение циклов длины, кратной 3, и путей. Пусть $I S$ — независимое множество в $GS,$ содержащее каждую третью вершину в каждом цикле и каждом пути. Итак $| Я С |$ содержит как минимум $.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}3| С | ⁄ 3 = | С |$ вершины. Пусть $J$ — независимое множество в $GS размера$ не более $| С | - 1$ . Поскольку расстояние между любыми двумя вершинами $не IS$ менее 3, каждая вершина $J$ смежна не более чем с одной $IS вершиной$ . Следовательно, существует хотя бы одна вершина $IS,$ не смежная ни с одной вершиной $J$ . Поэтому $I S$ является особенным для $S$ . По предыдущей теореме $G$ имеет ISR.

Условие, основанное на гомологической связности

Одно семейство условий основано на гомологической связности комплекса независимости подграфов. Для формулировки условий используются следующие обозначения:

$Ind(G)$ обозначает комплекс независимости графа $G$ (то есть абстрактный симплициальный комплекс , грани которого являются независимыми множествами в $G$ ).
$η H (X)$ обозначает гомологическую связность симплициального комплекса $X$ (т. е. наибольшее целое число $k$ такое, что первые $k$ групп гомологий $X$ тривиальны) плюс 2.
$[m]$ — набор индексов цветов, ${1, \dots, n}.$ Для любого подмножества $из$ [ $m] V$ J $J является$ объединением $V J$ для $J$ в $J.$ цветов
$G [VJ индуцированный]$ подграф $G,$ вершинами из $VJ .$ —

Следующее условие неявно вытекает из ^[9] и было явно доказано в. ^[10]

Если для всех подмножеств $J$ из $[m]$ :
$\eta _{H}({\text{Ind}}(G[V_{J}]))\geq |J|$
тогда раздел $V 1, \dots, V m$ допускает ISR.

В качестве примера: ^[4] предположим, что $G$ — двудольный граф , и его частями являются в точности $V 1$ и $V 2$ . В этом случае $[m] = {1,2},$ поэтому есть четыре варианта для $J$ :

$J = {}:$ тогда $G [J] = {}$ и $Ind(G [J]) = {}$ и связность бесконечна, поэтому условие выполняется тривиально.
$J = {1}:$ тогда $G [J]$ — граф с вершинами $V 1$ и без ребер. Здесь все множества вершин независимы, поэтому $Ind(G [J])$ является набором степеней $V 1$ , т.е. он имеет единственный $n$ -симплекс (и все его подмножества). Известно, что единственный симплекс является $k$ -связным для всех целых $k$ , поскольку все его приведенные группы гомологии тривиальны (см. симплициальные гомологии ). Следовательно, условие выполняется.
$J = {2}:$ этот случай аналогичен предыдущему.
$J = {1,2}:$ тогда $G [J] = G$ и $Ind(G)$ содержит два симплекса $V 1$ и $V 2$ (и все их подмножества). Условие $η H (Ind(G)) \geq 2$ эквивалентно условию гомологической связности $Ind(G)$ не меньше 0, что эквивалентно условию, что ${\tilde {H_{0}}}({\text{Ind}}(G))$ является тривиальной группой. Это справедливо тогда и только тогда, когда комплекс $Ind(G)$ содержит связь между двумя своими симплексами $V 1$ и $V 2$ . Такое соединение эквивалентно независимому множеству, в котором одна вершина из $V 1$ и одна из $V 2$ . Таким образом, в данном случае условие теоремы является не только достаточным, но и необходимым.

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

Каждый правильно раскрашенный треугольников x граф хроматического числа $без$ содержит независимый от радуги набор размером не менее $x ⁄ 2$ . ^[11]

Некоторые авторы изучали условия существования больших множеств, независимых от радуги, в различных классах графов. ^[1]^[12]

Вычисление

Проблема решения ISR — это проблема определения того, допускает ли данный граф $G = (V, E)$ и данное разбиение $V$ на $m$ цветов набор, независимый от радуги. Эта задача является NP-полной . Доказательство основано на трехмерной задаче сопоставления (3DM). ^[4] Входными данными для 3DM является трехсторонний гиперграф $(X + Y + Z, F)$ , где $X$ , $Y$ , $Z$ — наборы вершин размера $m$ , а $F$ — набор троек, каждый из которых содержит по одной вершине каждого из $Х$ , $Ю$ , $З.$ Входные данные для 3DM можно преобразовать во входные данные для ISR следующим образом:

Для каждого ребра $(x, y, z)$ в $F$ существует вершина $v x,y,z$ в $V$ ;
Для каждой вершины $z$ в $Z$ пусть $V z = {v x,y,z | х € Икс, у € Y}.$
каждых $x$ , $y1 Для$ , $y2 ($ , $z1 z1$ , $z2 $ ребро $, vx , y1 z2 в , vx, y2, )$ ; $E$ существует
Для каждых $x 1$ , $x 2$ , $y$ , $z 1$ , $z 2$ существует ребро $(v x 1, y, z 1, v x 2, y, z 2)$ в $E$ ;

В полученном графе $G = (V, E)$ ISR соответствует набору троек $(x, y, z)$ таких, что:

Каждый триплет имеет разное $значение z$ (поскольку каждый триплет принадлежит разному цветовому набору $V z$ );
Каждый триплет имеет разное $значение x$ и разное $значение y$ (поскольку вершины независимы).

Следовательно, результирующий граф допускает ISR тогда и только тогда, когда исходный гиперграф допускает 3DM.

Альтернативное доказательство — сокращение от SAT . ^[3]

Связанные понятия

Если $G$ — линейный граф некоторого другого графа $H$ , то независимые множества в $G$ это паросочетания в $H.$ — Следовательно, независимое от радуги множество в $G$ является радужным паросочетанием в $H$ . См. также сопоставление в гиперграфах .

Другая связанная концепция — это радужный цикл , который представляет собой цикл , в котором каждая вершина имеет свой цвет. ^[13]

Когда существует ISR, естественный вопрос заключается в том, существуют ли другие ISR, такие, что весь набор вершин разделен на непересекающиеся ISR (при условии, что количество вершин каждого цвета одинаково). Такое разбиение называется сильной раскраской .

Используя метафору факультета: ^[3]

Система отдельных представителей — это комитет отдельных членов, с конфликтами или без них.
— Независимая группа это бесконфликтный комитет.
Независимый трансверсал — это бесконфликтный комитет, в состав которого входит ровно один член от каждого отдела.
— Раскраска графа это бесконфликтное разделение преподавателей на комитеты.
Яркой окраской является бесконфликтное разделение преподавателей на комитеты, в состав которых входит ровно один член от каждой кафедры. Поэтому эту проблему иногда называют проблемой счастливого декана .

Радужная клика или цветная клика — это клика , в которой каждая вершина имеет свой цвет. ^[10] Каждая клика в графе соответствует независимому множеству в графе дополнений . Следовательно, каждая радужная клика в графе соответствует независимому от радуги множеству в графе-дополнении.

См. также

Ссылки

^ Jump up to: ^а ^б Ахарони, Рон; Бриггс, Джозеф; Ким, Джинха; Ким, Минки (28 сентября 2019 г.). «Радужные независимые множества в некоторых классах графов». arXiv : 1909.13143 [ math.CO ].
^ Ахарони, Рон; Бергер, Эли; Котлар, Дэни; Зив, Ран (01 октября 2017 г.). «О догадке камня». Трактаты математического семинара Гамбургского университета . 87 (2): 203–211. дои : 10.1007/s12188-016-0160-3 . ISSN 1865-8784 . S2CID 119139740 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Хакселл, П. (1 ноября 2011 г.). «О формировании комиссий». Американский математический ежемесячник . 118 (9): 777–788. doi : 10.4169/amer.math.monthly.118.09.777 . ISSN 0002-9890 . S2CID 27202372 .
^ Jump up to: ^а ^б ^с ^д Ахарони, Рон; Бергер, Эли; Зив, Ран (1 мая 2007 г.). «Независимые системы представителей во взвешенных графах». Комбинаторика . 27 (3): 253–267. дои : 10.1007/s00493-007-2086-y . ISSN 1439-6912 . S2CID 43510417 .
^ Э, Хакселл П. (1 июля 2001 г.). «Заметка о раскраске списка вершин». Комбинаторика, теория вероятностей и вычисления . 10 (4): 345–347. дои : 10.1017/s0963548301004758 . S2CID 123033316 .
^ Сабо*, Тибор; Тардос †, Габор (1 июня 2006 г.). «Экстремальные задачи для трансверсалей в графах с ограниченной степенью». Комбинаторика . 26 (3): 333–351. дои : 10.1007/s00493-006-0019-9 . hdl : 20.500.11850/24692 . ISSN 1439-6912 . S2CID 15413015 .
^ Хакселл, Пенни; Сабо, Тибор (1 января 2006 г.). «Нечетные независимые трансверсали нечетны» . Комбинаторика, теория вероятностей и вычисления . 15 (1–2): 193–211. дои : 10.1017/S0963548305007157 . ISSN 1469-2163 . S2CID 6067931 .
^ Берке, Роберт; Хакселл, Пенни; Сабо, Тибор (2012). «Ограниченные трансверсали в многодольных графах». Журнал теории графов . 70 (3): 318–331. дои : 10.1002/jgt.20618 . ISSN 1097-0118 . S2CID 17608344 .
^ Jump up to: ^а ^б Ахарони, Рон; Хакселл, Пенни (2000). «Теорема Холла для гиперграфов» . Журнал теории графов . 35 (2): 83–88. doi : 10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V . ISSN 1097-0118 .
^ Jump up to: ^а ^б Мешулам, Рой (1 января 2001 г.). «Комплекс клик и сопоставление гиперграфов». Комбинаторика . 21 (1): 89–94. дои : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .
^ Аравинд, Северная Каролина; Камби, Стейн; ван Батенбург, Воутер Камес; де Веркло, Реми де Жоаннис; Канг, Росс Дж.; Патель, Виреш (15 марта 2020 г.). «Структура и цвет в графах без треугольников». arXiv : 1912.13328 [ math.CO ].
^ Ким, Джинха; Ким, Минки; Квон, О.-Чжон (05 февраля 2020 г.). «Радужные независимые множества на классах плотных графов». arXiv : 2001.10566 [ math.CO ].
^ Ахарони, Рон; Бриггс, Джозеф; Хольцман, Рон; Цзян, Цзилинь (2021). «Радужные нечетные циклы». SIAM Journal по дискретной математике . 35 (4): 2293–2303. arXiv : 2007.09719 . дои : 10.1137/20M1380557 . S2CID 220647170 .

[:0-1] Jump up to: ^а ^б Ахарони, Рон; Бриггс, Джозеф; Ким, Джинха; Ким, Минки (28 сентября 2019 г.). «Радужные независимые множества в некоторых классах графов». arXiv : 1909.13143 [ math.CO ].

[2] Ахарони, Рон; Бергер, Эли; Котлар, Дэни; Зив, Ран (01 октября 2017 г.). «О догадке камня». Трактаты математического семинара Гамбургского университета . 87 (2): 203–211. дои : 10.1007/s12188-016-0160-3 . ISSN 1865-8784 . S2CID 119139740 .

[:2-3] Jump up to: ^а ^б ^с ^д ^и ^ж Хакселл, П. (1 ноября 2011 г.). «О формировании комиссий». Американский математический ежемесячник . 118 (9): 777–788. doi : 10.4169/amer.math.monthly.118.09.777 . ISSN 0002-9890 . S2CID 27202372 .

[:1-4] Jump up to: ^а ^б ^с ^д Ахарони, Рон; Бергер, Эли; Зив, Ран (1 мая 2007 г.). «Независимые системы представителей во взвешенных графах». Комбинаторика . 27 (3): 253–267. дои : 10.1007/s00493-007-2086-y . ISSN 1439-6912 . S2CID 43510417 .

[5] Э, Хакселл П. (1 июля 2001 г.). «Заметка о раскраске списка вершин». Комбинаторика, теория вероятностей и вычисления . 10 (4): 345–347. дои : 10.1017/s0963548301004758 . S2CID 123033316 .

[6] Сабо*, Тибор; Тардос †, Габор (1 июня 2006 г.). «Экстремальные задачи для трансверсалей в графах с ограниченной степенью». Комбинаторика . 26 (3): 333–351. дои : 10.1007/s00493-006-0019-9 . hdl : 20.500.11850/24692 . ISSN 1439-6912 . S2CID 15413015 .

[7] Хакселл, Пенни; Сабо, Тибор (1 января 2006 г.). «Нечетные независимые трансверсали нечетны» . Комбинаторика, теория вероятностей и вычисления . 15 (1–2): 193–211. дои : 10.1017/S0963548305007157 . ISSN 1469-2163 . S2CID 6067931 .

[8] Берке, Роберт; Хакселл, Пенни; Сабо, Тибор (2012). «Ограниченные трансверсали в многодольных графах». Журнал теории графов . 70 (3): 318–331. дои : 10.1002/jgt.20618 . ISSN 1097-0118 . S2CID 17608344 .

[:4-9] Jump up to: ^а ^б Ахарони, Рон; Хакселл, Пенни (2000). «Теорема Холла для гиперграфов» . Журнал теории графов . 35 (2): 83–88. doi : 10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V . ISSN 1097-0118 .

[:3-10] Jump up to: ^а ^б Мешулам, Рой (1 января 2001 г.). «Комплекс клик и сопоставление гиперграфов». Комбинаторика . 21 (1): 89–94. дои : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .

[11] Аравинд, Северная Каролина; Камби, Стейн; ван Батенбург, Воутер Камес; де Веркло, Реми де Жоаннис; Канг, Росс Дж.; Патель, Виреш (15 марта 2020 г.). «Структура и цвет в графах без треугольников». arXiv : 1912.13328 [ math.CO ].

[12] Ким, Джинха; Ким, Минки; Квон, О.-Чжон (05 февраля 2020 г.). «Радужные независимые множества на классах плотных графов». arXiv : 2001.10566 [ math.CO ].

[13] Ахарони, Рон; Бриггс, Джозеф; Хольцман, Рон; Цзян, Цзилинь (2021). «Радужные нечетные циклы». SIAM Journal по дискретной математике . 35 (4): 2293–2303. arXiv : 2007.09719 . дои : 10.1137/20M1380557 . S2CID 220647170 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]