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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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

[:0-1] Перейти обратно: ^а ^б ^с ^д Мешулам, Рой (1 мая 2003 г.). «Числа доминирования и гомологии» . Журнал комбинаторной теории, серия А. 102 (2): 321–330. дои : 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 .

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

[6] Бьорнер, А.; Ловас, Л.; Вречица, СТ; Живальевич, RT (1994). «Шахматные комплексы и согласующие комплексы». Журнал Лондонского математического общества . 49 (1): 25–39. дои : 10.1112/jlms/49.1.25 . ISSN 1469-7750 .

[7] Райнер, Виктор; Робертс, Джоэл (1 марта 2000 г.). «Минимальные разрешения и гомология совпадающих и шахматных комплексов» . Журнал алгебраической комбинаторики . 11 (2): 135–154. дои : 10.1023/A:1008728115910 . ISSN 1572-9192 .

[8] Фридман, Джоэл; Хэнлон, Фил (1 сентября 1998 г.). «О числах Бетти шахматных комплексов» . Журнал алгебраической комбинаторики . 8 (2): 193–203. дои : 10.1023/А:1008693929682 . hdl : 2027.42/46302 . ISSN 1572-9192 .

[9] Циглер, Гюнтер М. (1 февраля 1994 г.). «Обстреливаемость шахматных комплексов». Израильский математический журнал . 87 (1): 97–110. дои : 10.1007/BF02772986 . ISSN 1565-8511 . S2CID 59040033 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]