Комплекс Независимости

Комплекс независимости графа — это математический объект, описывающий независимые множества графа. Формально комплекс независимости неориентированного графа G , обозначаемый I( G ), является абстрактным симплициальным комплексом (то есть семейством конечных множеств, замкнутым относительно операции взятия подмножеств), образованным множествами вершин в независимых множествах G . Любое подмножество независимого множества само является независимым множеством, поэтому I( G ) действительно замкнуто относительно взятия подмножеств.

Каждое независимое множество в графе является кликой в ​​его дополнительном графе , и наоборот. Таким образом, комплекс независимости графа равен комплексу клик его дополнительного графа, и наоборот.

Группы гомологии

Несколько авторов изучали связи между свойствами графа G = ( V , E ) и группами гомологий его комплекса независимости I( G ). ^[1] В частности, несколько свойств, связанных с доминирующими множествами в G, гарантируют, что некоторые редуцированные группы гомологий I( G ) являются тривиальными.

1. Общее доминирующее число G, обозначаемое , является минимальной мощностью полного доминирующего множества G - множества S, такого, что каждая вершина V смежна с вершиной S. Если , то . ^[2] ${\displaystyle \gamma _{0}(G)}$ ${\displaystyle \gamma _{0}(G)>k}$ ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

2. Общее число доминирования подмножества A множества V в G, обозначаемое , является минимальной мощностью множества S, такой что каждая вершина A смежна с вершиной S . Число доминирования независимости G, обозначаемое , является максимальным значением среди всех независимых множеств A в G . Если , то . ^{[1] [3]} ${\displaystyle \gamma _{0}(G,A)}$ ${\displaystyle i\gamma (G)}$ ${\displaystyle \gamma _{0}(G,A)}$ ${\displaystyle i\gamma (G)>k}$ ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

3. Число доминирования графа G , обозначаемое , представляет собой минимальную мощность доминирующего множества графа G — множества S, такого, что каждая вершина графа V \ S смежна с вершиной графа S. Обратите внимание, что . Если граф G является хордовым , то . ^[4] ${\displaystyle \gamma (G)}$ ${\displaystyle \gamma _{0}(G)\geq \gamma (G)}$ ${\displaystyle \gamma (G)>k}$ ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

4. Число индуцированных соответствий G , обозначаемое , является наибольшей мощностью индуцированного соответствий в G - соответствий, включающих каждое ребро, соединяющее любые две вершины в подмножестве. Если существует подмножество A из V такое , что , то . ^[5] Это обобщение обоих свойств 1 и 2 выше. ${\displaystyle \mu (G)}$ ${\displaystyle \gamma _{0}(G,A)>k+\min[k,\mu (G[A])]}$ ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

5. Недоминирующий независимый комплекс G, обозначаемый I'( G ), является абстрактным симплициальным комплексом независимых множеств, которые не являются доминирующими множествами G . Очевидно, что I'( G ) содержится в I( G ); обозначим отображение включения через . Если G является хордовым графом , то индуцированное отображение равно нулю для всех . ^{[1] : Теор.1.4} Это обобщение свойства 3 выше . ${\displaystyle i:I'(G)\to I(G)}$ ${\displaystyle i_{*}:{\tilde {H}}_{k}(I'(G))\to {\tilde {H}}_{k}(I(G))}$ ${\displaystyle k\geq -1}$

6. Дробное число звездного доминирования G, обозначаемое , является минимальным размером дробного звездного доминирования множества в G. Если , то . ^{[1] : Теор.1.5} ${\displaystyle \gamma _{s}^{*}(G)}$ ${\displaystyle \gamma _{s}^{*}(G)>k}$ ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

Связанные концепции

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

Комплекс паросочетаний графа G , обозначаемый M( G ), является абстрактным симплициальным комплексом паросочетаний в G . Это комплекс независимости линейного графа графа G . ^{[6] [7]}

Комплекс ( m , n )-шахматной доски — это комплекс соответствия на полном двудольном графе K _m , _n . Это абстрактный симплициальный комплекс всех множеств позиций на шахматной доске m на n , на которые можно поставить ладьи так, чтобы они не угрожали друг другу. ^{[8] [9]}

Комплекс клик графа G является комплексом независимости графа дополнений графа G.

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

• Радужно-независимый набор

Ссылки

1. Мешулам, Рой (2003-05-01). "Числа доминирования и гомология". Журнал комбинаторной теории, серия A. 102 ( 2): 321–330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN  0097-3165.
2. Чудновски, Мария (2000). Системы непересекающихся представителей (диссертация на степень магистра наук) . Хайфа, Израиль: Технион, кафедра математики.
3. Ахарони, Рон; Хакселл, Пенни (2000). «Теорема Холла для гиперграфов». Журнал теории графов . 35 (2): 83–88. doi :10.1002/1097-0118(200010)35:2<83::aid-jgt2>3.0.co;2-v. ISSN  0364-9024.
4. Ахарони, Рон; Бергер, Эли; Зив, Ран (1 июля 2002 г.). «Древовидная версия теоремы Кенига». Комбинаторика . 22 (3): 335–343. дои : 10.1007/s004930200016. ISSN  0209-9683. S2CID  38277360.
5. Мешулам, Рой (01.01.2001). «Комплекс клик и соответствие гиперграфов». Combinatorica . 21 (1): 89–94. doi :10.1007/s004930170006. ISSN  1439-6912. S2CID  207006642.
6. Бьёрнер, А.; Ловас, Л.; Вречица, СТ; Живальевич, РТ (1994). «Комплексы шахматной доски и соответствующие комплексы». Журнал Лондонского математического общества . 49 (1): 25–39. doi :10.1112/jlms/49.1.25. ISSN  1469-7750.
7. Райнер, Виктор; Робертс, Джоэл (2000-03-01). «Минимальные резолюции и гомологии комплексов соответствия и шахматной доски». Журнал алгебраической комбинаторики . 11 (2): 135–154. doi : 10.1023/A:1008728115910 . ISSN  1572-9192.
8. Фридман, Джоэл; Хэнлон, Фил (1998-09-01). «О числах Бетти шахматных комплексов». Журнал алгебраической комбинаторики . 8 (2): 193–203. doi : 10.1023/A:1008693929682 . hdl : 2027.42/46302 . ISSN  1572-9192.
9. Циглер, Гюнтер М. (1994-02-01). «Оболочкообразуемость шахматных комплексов». Israel Journal of Mathematics . 87 (1): 97–110. doi :10.1007/BF02772986. ISSN  1565-8511. S2CID  59040033.