Кликовый комплекс

Комплексы клик , комплексы независимости, комплексы флагов , комплексы Уитни и конформные гиперграфы — это тесно связанные математические объекты в теории графов и геометрической топологии , каждый из которых описывает клики (полные подграфы) неориентированного графа .

Кликовый комплекс

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

Комплекс клик также можно рассматривать как топологическое пространство , в котором каждая клика из $k$ вершин представлена симплексом размерности k $- 1$ . X 1-скелет ( $; G) ($ также известный как основной граф комплекса) представляет собой неориентированный граф с вершиной для каждого набора из 1 элемента в семействе и ребром для каждого набора из 2 элементов в семействе он изоморфен G $$ . ^[1]

Отрицательный пример

Каждый комплекс клики является абстрактным симплициальным комплексом, но обратное неверно. Например, рассмотрим абстрактный симплициальный комплекс над ${1,2,3,4}$ с максимальными множествами ${1,2,3},$ ${2,3,4},$ ${4,1}.$ Если бы это был $X (G)$ некоторого графа $G$ , то $G$ должен был бы иметь ребра ${1,2},$ ${1,3},$ ${2,3},$ ${2,4},$ ${3,4},$ ${4,1},$ поэтому $X (G)$ также должен содержать клику ${1,2,3,4}.$

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

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

Флаговый комплекс

Комплекс флагов — это абстрактный симплициальный комплекс с дополнительным свойством, называемым «2-определенным»: для каждого подмножества S вершин, если каждая пара вершин в S находится в комплексе, то сам S тоже находится в комплексе.

Каждый комплекс клик является комплексом флагов: если каждая пара вершин в S является кликой размера 2, то между ними есть ребро, поэтому S является кликой.

Каждый комплекс флагов является комплексом клики: для данного комплекса флагов определите граф G на множестве всех вершин, где две вершины u,v смежны в G тогда и только тогда, когда {u,v} находится в комплексе (этот граф называется 1-скелет комплекса). По определению комплекса флагов, каждый набор попарно связанных вершин входит в комплекс. Следовательно, комплекс флагов равен комплексу клики на G .

Таким образом, комплексы флагов и комплексы клик — это, по сути, одно и то же. Однако во многих случаях удобно определять комплекс флагов непосредственно на основе некоторых данных, отличных от графа, а не косвенно как комплекс клик графа, полученного на основе этих данных. ^[2]

Михаил Громов определил условие no-Δ как условие флагового комплекса.

Комплекс Уитни

Кликовые комплексы также известны как комплексы Уитни , в честь Хасслера Уитни . Триангуляция Уитни или чистая триангуляция двумерного многообразия — это вложение графа $G$ в многообразие таким образом, что каждая грань является треугольником, а каждый треугольник — гранью. Если граф $G$ имеет триангуляцию Уитни, он должен образовывать клеточный комплекс, изоморфный комплексу Уитни $G.$ графа В этом случае комплекс (рассматриваемый как топологическое пространство) гомеоморфен лежащему в основе многообразию. Граф $G$ имеет комплекс клик 2-многообразий и может быть вложен как триангуляция Уитни тогда и только тогда, когда $G$ цикличен локально ; это означает, что для каждой вершины $v$ в графе индуцированный подграф , образованный соседями вершины $v,$ образует один цикл. ^[3]

Конформный гиперграф

Первичный граф G ( H ) гиперграфа — это граф на одном и том же множестве вершин, ребрами которого являются пары вершин, входящие вместе в одно и то же гиперребро . Гиперграф называется конформным, если каждая максимальная клика его первичного графа является гиперребром или, что то же самое, если каждая клика его первичного графа содержится в некотором гиперребре. ^[4] Если требуется, чтобы гиперграф был замкнутым вниз (чтобы он содержал все гиперребра, содержащиеся в некотором гиперребре), то гиперграф является конформным именно тогда, когда он является комплексом флагов. Это роднит язык гиперграфов с языком симплициальных комплексов.

Примеры и приложения

Барицентрическое подразделение любого клеточного комплекса C представляет собой комплекс флагов, имеющий одну вершину на C. ячейку Набор вершин барицентрического подразделения образует симплекс тогда и только тогда, когда соответствующий набор ячеек C образует флаг (цепь в порядке включения ячеек). ^[2] В частности, барицентрическое подразделение клеточного комплекса на 2-многообразие приводит к триангуляции Уитни многообразия.

Порядковый комплекс состоит частично упорядоченного множества из цепей ( полностью упорядоченных подмножеств) частичного порядка. Если каждая пара некоторого подмножества сама по себе упорядочена, то все подмножество представляет собой цепь, поэтому комплекс порядка удовлетворяет условию отсутствия Δ. Его можно интерпретировать как кликовый комплекс графа сравнимости частичного порядка. ^[2]

Соответствующий комплекс графа состоит из наборов ребер, ни одно из которых не имеет общей конечной точки; опять же, это семейство множеств удовлетворяет условию отсутствия Δ. Его можно рассматривать как кликовый комплекс графа -дополнения линейного графа данного графа. Когда комплекс сопоставления упоминается без какого-либо конкретного графа в качестве контекста, это означает комплекс сопоставления полного графа . Комплекс согласования полного двудольного графа , _{Km n известен} как комплекс шахматной доски . Это граф клики графа дополнения ладейного графа , ^[5] и каждый из его симплексов представляет собой такое расположение ладей на шахматной доске m × n , при котором никакие две ладьи не атакуют друг друга. Когда m = n ± 1, шахматный комплекс образует псевдомногообразие .

Комплекс Виеториса – Рипса набора точек в метрическом пространстве является частным случаем комплекса клик, образованного из единичного дискового графа точек; однако каждый комплекс клики (G) можно интерпретировать как комплекс Виеториса–Рипса метрики кратчайшего пути на базовом графе G. X

Ходкинсон и Отто (2003) описывают применение конформных гиперграфов в логике реляционных структур. В этом контексте граф Гейфмана реляционной структуры аналогичен базовому графу гиперграфа, представляющего структуру, и структура защищена, если она соответствует конформному гиперграфу.

Громов показал, что кубический комплекс (то есть семейство гиперкубов, пересекающихся лицом к лицу) образует CAT(0)-пространство тогда и только тогда, когда комплекс односвязен и связь каждой вершины образует флаговый комплекс. Кубический комплекс, отвечающий этим условиям, иногда называют кубом или пространством со стенами . ^[1]^[6]

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

Мешулам ^[7] доказывает следующую теорему о гомологии комплекса клики. Данные целые числа $l\geq 1,t\geq 0$ , предположим, что граф G удовлетворяет свойству, называемому $P(l,t)$ , что означает, что:

Каждый набор $l$ вершины в G имеют общего соседа;
Существует множество вершин A , содержащее общего соседа для каждого множества вершин. $l$ вершин, и, кроме того, индуцированный граф G [ A ] не содержит в качестве индуцированного подграфа копию 1-скелета октаэдрической t -мерной сферы .

Тогда j -я приведенная гомология комплекса клики X( G ) тривиальна для любого j между 0 и $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ .

См. также

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

Примечания

^ Jump up to: ^а ^б Бандельт и Чепой (2008) .
^ Jump up to: ^а ^б ^с Дэвис (2002) .
^ Хартсфельд и Рингель (1991) ; Ларрион, Нойманн-Лара и Пизанья (2002) ; Мальнич и Мохар (1992) .
^ Берге (1989) ; Ходкинсон и Отто (2003) .
^ Донг и Вакс (2002) .
^ Чаттерджи и Нибло (2005) .
^ Мешулам, Рой (1 января 2001 г.). «Комплекс клик и сопоставление гиперграфов». Комбинаторика . 21 (1): 89–94. дои : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .

Ссылки

Бандельт, Х.-Ю.; Чепой, В. (2008), «Метрическая теория графов и геометрия: обзор», в Гудмане, Дж. Э .; Пах, Дж .; Поллак Р. (ред.), Обзоры по дискретной и вычислительной геометрии: двадцать лет спустя (PDF) , Contemporary Mathematics, vol. 453, Провиденс, Род-Айленд: AMS, стр. 49–86 .
Берге, К. (1989), Гиперграфы: комбинаторика конечных множеств , Северная Голландия, ISBN 0-444-87489-5 .
Чаттерджи, И .; Нибло, Г. (2005), «От пространств стен до кубических комплексов CAT (0)», Международный журнал алгебры и вычислений , 15 (5–6): 875–885, arXiv : math.GT/0309036 , doi : 10.1142 /S0218196705002669 , S2CID 2786607 .
Дэвис, М.В. (2002), «Группы неположительной кривизны и отражения», в Давермане, Р.Дж .; Шер, Р.Б. (ред.), Справочник по геометрической топологии , Elsevier, стр. 373–422 .
Донг, X.; Вакс, М.Л. (2002), «Комбинаторный лапласиан согласующего комплекса» , Электронный журнал комбинаторики , 9 : R17, doi : 10.37236/1634 .
Хартсфельд, Н.; Рингель, Герхард (1991), «Чистые триангуляции», Combinatorica , 11 (2): 145–155, doi : 10.1007/BF01206358 , S2CID 28144260 .
Ходкинсон, И.; Отто, М. (2003), «Конечные конформные гиперграфические покрытия и клики Гейфмана в конечных структурах», Бюллетень символической логики , 9 (3): 387–405, CiteSeerX 10.1.1.107.5000 , doi : 10.2178/bsl/1058448678 .
Ларрион, Ф.; Нойманн-Лара, В .; Писанья, Массачусетс (2002), «Триангуляции Уитни, локальный обхват и итерированные графы клик» , Discrete Mathematics , 258 (1–3): 123–135, doi : 10.1016/S0012-365X(02)00266-2 .
Мальнич, А.; Мохар, Б. (1992), «Генерация локально циклических триангуляций поверхностей», Журнал комбинаторной теории, серия B , 56 (2): 147–164, doi : 10.1016/0095-8956(92)90015-P .

[bc-1] Jump up to: ^а ^б Бандельт и Чепой (2008) .

[davis-2] Jump up to: ^а ^б ^с Дэвис (2002) .

[3] Хартсфельд и Рингель (1991) ; Ларрион, Нойманн-Лара и Пизанья (2002) ; Мальнич и Мохар (1992) .

[4] Берге (1989) ; Ходкинсон и Отто (2003) .

[5] Донг и Вакс (2002) .

[6] Чаттерджи и Нибло (2005) .

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]