Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
«Комплекс Уитни» перенаправляется сюда. Для спортивного сооружения Миссисипи см Davey Whitney Complex .
Кликовый комплекс графа. Клики первого размера показаны маленькими красными дисками; клики размера два показаны как сегменты черной линии; клики третьего размера показаны голубыми треугольниками; клики размера четыре показаны темно-синими тетраэдрами.

Clique комплексы , флаг комплексы и конформные гиперграфы тесно связаны между собой математическими объектами в теории графов и геометрической топологии , что каждые описывают клики (полные подграфы) требуемый неориентированного граф .

Клика комплекс Х ( G ) неориентированный граф G является абстрактным симплициальным комплексом (то есть семейство конечных множеств замкнуто относительно операции взятия подмножеств), образованных множеств вершин в кликах G . Любое подмножество клики само по себе является кликой, поэтому это семейство множеств удовлетворяет требованию абстрактного симплициального комплекса, согласно которому каждое подмножество множества в семействе также должно быть в семействе. Клика комплекс также можно рассматривать как топологическое пространство , в котором каждая Клика K вершин представлена симплексом размерности к  - 1. 1-скелет из X ( G) (также известный как базовый граф комплекса) - неориентированный граф с вершиной для каждого набора из 1 элемента в семействе и ребром для каждого набора из 2 элементов в семействе; она изоморфна  G . [1]

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

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

Флаговый комплекс [ править ]

Флаг комплекс представляет собой абстрактная симплициальный комплекс таким образом, что каждое множество вершин , в которой все пары являются лицом комплекса также сам по себе является грань комплекса. Таким образом, комплексы флагов и клики - это, по сути, одно и то же. Любой флаговый комплекс - это кликовый комплекс своего 1-скелета. Однако во многих случаях удобно определять комплекс флагов непосредственно из некоторых данных, отличных от графа, а не косвенно как кликовый комплекс графа, полученного из этих данных. [3]

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

Конформный гиперграф [ править ]

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

Примеры и приложения [ править ]

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

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

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

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

Hodkinson & Otto (2003) описывают применение конформных гиперграфов в логике реляционных структур. В этом контексте граф Гайфмана реляционной структуры совпадает с нижележащим графом гиперграфа, представляющего структуру, и структура охраняется, если она соответствует конформному гиперграфу.

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

Группы гомологий [ править ]

Мешулам [7] доказывает следующую теорему о гомологиях кликового комплекса. Даны целые числа , предположим, что граф G удовлетворяет названному свойству , что означает, что:

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

Тогда j -я приведенная гомология кликового комплекса X ( G ) тривиальна для любого j между 0 и .

См. Также [ править ]

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

Заметки [ править ]

  1. ^ a b Bandelt & Chepoi (2008) .
  2. ^ Хартсфельд и Рингель (1991) ; Ларрион, Нойман-Лара и Писанья (2002) ; Малнич и Мохар (1992) .
  3. ^ а б в Дэвис (2002) .
  4. ↑ Berge (1989) ; Ходкинсон и Отто (2003) .
  5. ^ Dong & Wachs (2002) .
  6. ↑ Чаттерджи и Нибло (2005) .
  7. ^ Мешулам, Рой (2001-01-01). «Кликовый комплекс и соответствие гиперграфа». Combinatorica . 21 (1): 89–94. DOI : 10.1007 / s004930170006 . ISSN  1439-6912 . S2CID  207006642 .

Ссылки [ править ]

  • Bandelt, H.J .; Чепой, В. (2008), "Метрическая теория графов и геометрия: обзор", в Goodman, JE ; Pach, J .; Поллак, Р. (ред.), Обзоры дискретной и вычислительной геометрии: двадцать лет спустя (PDF) , Современная математика, 453 , Провиденс, Род-Айленд: AMS, стр. 49–86.
  • Берге, К. (1989), Гиперграфы: комбинаторика конечных множеств , Северная Голландия, ISBN 0-444-87489-5.
  • Chatterji, I .; Нибло, Г. (2005), «От стеновых пространств до комплексов кубов CAT (0)», Международный журнал алгебры и вычислений , 15 (5–6): 875–885, arXiv : math.GT/0309036 , doi : 10.1142 / S0218196705002669 , S2CID  2786607.
  • Дэвис, MW (2002), "Неположительные группы кривизны и отражения", в Давермане, RJ; Шер, РБ (ред.), Справочник по геометрической топологии , Elsevier, стр. 373–422..
  • Донг, X .; Вакс, ML (2002), "Комбинаторный лапласиан согласования комплекса" , Электронный журнал комбинаторика , 9 : R17, DOI : 10,37236 / 1634.
  • Hartsfeld, N .; Рингель, Gerhard (1991), "Чистые триангуляции", Combinatorica , 11 (2): 145-155, DOI : 10.1007 / BF01206358 , S2CID  28144260.
  • Hodkinson, I .; Отто, М. (2003), "Конечные покрытия конформного гиперграфа и Gaifman клика в конечных структурах", Бюллетень символической логики , 9 (3): 387-405, CiteSeerX  10.1.1.107.5000 , DOI : 10,2178 / BSL / 1058448678.
  • Ларрион, Ф .; Нойман-Лара, В .; Pizaña, MA (2002), "Уитня триангуляция, локальная обхват и итерация кружковых граф" , Дискретная математика , 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.