Комплексы клик , комплексы независимости, комплексы флагов , комплексы Уитни и конформные гиперграфы — тесно связанные математические объекты в теории графов и геометрической топологии , каждый из которых описывает клики (полные подграфы) неориентированного графа .
Кликовый комплекс X ( G ) неориентированного графа G является абстрактным симплициальным комплексом (то есть семейством конечных множеств, замкнутым относительно операции взятия подмножеств), образованным множествами вершин в кликах графа G . Любое подмножество клики само является кликой, поэтому это семейство множеств удовлетворяет требованию абстрактного симплициального комплекса, что каждое подмножество множества в семействе также должно быть в этом семействе .
Комплекс клик также можно рассматривать как топологическое пространство , в котором каждая клика из k вершин представлена симплексом размерности k – 1. 1 -скелет X ( 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]
Михаил Громов определил условие отсутствия Δ как условие существования флагового комплекса.
Кликовые комплексы также известны как комплексы Уитни , в честь Хасслера Уитни . Триангуляция Уитни или чистая триангуляция двумерного многообразия — это вложение графа G в многообразие таким образом, что каждая грань является треугольником, а каждый треугольник — гранью. Если граф G имеет триангуляцию Уитни, он должен образовывать клеточный комплекс, изоморфный комплексу Уитни графа G. В этом случае комплекс (рассматриваемый как топологическое пространство) гомеоморфен базовому многообразию. Граф G имеет 2-многообразный кликовый комплекс и может быть вложен как триангуляция Уитни, если и только если G локально цикличен ; это означает, что для каждой вершины v в графе индуцированный подграф , образованный соседями v, образует один цикл. [3]
Первичный граф G ( H ) гиперграфа — это граф на том же множестве вершин, имеющий в качестве своих ребер пары вершин, появляющиеся вместе в одном и том же гиперребре . Гиперграф называется конформным, если каждая максимальная клика его первичного графа является гиперребром, или, что эквивалентно, если каждая клика его первичного графа содержится в некотором гиперребре. [4] Если гиперграф должен быть замкнутым вниз (то есть содержать все гиперребра, содержащиеся в некотором гиперребре), то гиперграф конформен именно тогда, когда он является флаговым комплексом. Это связывает язык гиперграфов с языком симплициальных комплексов.
Барицентрическое подразделение любого клеточного комплекса C является комплексом флагов, имеющим одну вершину на ячейку C. Набор вершин барицентрического подразделения образует симплекс тогда и только тогда, когда соответствующий набор ячеек C образует флаг (цепь в порядке включения ячеек). [2] В частности, барицентрическое подразделение клеточного комплекса на 2-многообразии приводит к триангуляции Уитни многообразия.
Порядковый комплекс частично упорядоченного множества состоит из цепей ( полностью упорядоченных подмножеств) частичного порядка. Если каждая пара некоторого подмножества сама упорядочена, то все подмножество является цепью, поэтому порядковый комплекс удовлетворяет условию no-Δ. Его можно интерпретировать как кликовый комплекс графа сравнимости частичного порядка. [2]
Соответствующий комплекс графа состоит из множеств ребер, никакие два из которых не имеют общей конечной точки; снова, это семейство множеств удовлетворяет условию no-Δ. Его можно рассматривать как кликовый комплекс графа- дополнения линейного графа данного графа. Когда комплекс-соответствие упоминается без какого-либо конкретного графа в качестве контекста, он означает комплекс-соответствие полного графа . Комплекс-соответствие полного двудольного графа K m , n известен как комплекс шахматной доски . Это граф клик графа-дополнения графа ладьи , [ 5] и каждый из его симплексов представляет собой размещение ладей на шахматной доске m × n таким образом, что никакие две ладьи не атакуют друг друга. Когда m = n ± 1, комплекс шахматной доски образует псевдомногообразие .
Комплекс Виеториса–Рипса множества точек в метрическом пространстве является частным случаем комплекса клик, образованного из графа единичного круга точек; однако каждый комплекс клик X (G) можно интерпретировать как комплекс Виеториса–Рипса метрики кратчайшего пути на базовом графе G.
Ходкинсон и Отто (2003) описывают применение конформных гиперграфов в логике реляционных структур. В этом контексте граф Гайфмана реляционной структуры совпадает с базовым графом гиперграфа, представляющего структуру, и структура охраняется, если она соответствует конформному гиперграфу.
Громов показал, что кубический комплекс (то есть семейство гиперкубов, пересекающихся лицом к лицу) образует пространство CAT(0) тогда и только тогда, когда комплекс односвязен и связь каждой вершины образует комплекс флагов. Кубический комплекс, удовлетворяющий этим условиям, иногда называют кубированием или пространством со стенами . [1] [6]
Мешулам [7] доказывает следующую теорему о гомологии комплекса клик. Для заданных целых чисел предположим, что граф G удовлетворяет свойству, называемому , что означает, что:
Тогда j -я редуцированная гомология кликового комплекса X( G ) тривиальна для любого j между 0 и .
