Абстрактный симплициальный комплекс

В комбинаторике абстрактный симплициальный комплекс (АСК), часто называемый абстрактным комплексом или просто комплексом , представляет собой семейство множеств , замкнутое относительно взятия подмножеств , т. е. каждое подмножество множества в семействе также находится в семействе. Это чисто комбинаторное описание геометрического понятия симплициального комплекса . ^[1] Например, в двумерном симплициальном комплексе множествами в семействе являются треугольники (наборы размера 3), их ребра (наборы размера 2) и их вершины (наборы размера 1).

В контексте матроидов и гридоидов абстрактные симплициальные комплексы также называются системами независимости . ^[2]

Абстрактный симплекс можно изучать алгебраически, образуя его кольцо Стэнли – Рейснера ; это устанавливает мощную связь между комбинаторикой и коммутативной алгеброй .

Определения [ править ]

Совокупность $∆$ непустых конечных подмножеств множества S называется семейством множеств.

Семейство множеств $Δ$ называется абстрактным симплициальным комплексом , если для любого множества $X$ из $Δ$ и каждого непустого подмножества $Y \subseteq X$ множество $Y$ также принадлежит $Δ$ .

Конечные множества, принадлежащие $Δ$ , называются гранями комплекса, а грань $Y$ считается принадлежащей другой грани $X$ , если $Y \subseteq X$ , поэтому определение абстрактного симплициального комплекса можно переформулировать следующим образом: каждая грань грани комплекса $∆$ сама является гранью $∆$ . Множество вершин Δ $,$ определяется как $V (Δ) = \cupΔ$ объединение всех граней $Δ$ . Элементы множества вершин называются вершинами комплекса. Для каждой вершины v группы $Δ$ множество { v } является гранью комплекса, а каждая грань комплекса является конечным подмножеством множества вершин.

Максимальные грани $Δ$ (т. е. грани, которые не являются подмножествами других граней) называются гранями комплекса. Размерность грани $X$ в $Δ$ определяется как $dim(X) = | Х | - 1$ : грани, состоящие из одного элемента, являются нульмерными, грани, состоящие из двух элементов, являются одномерными и т. д. Размерность комплекса $dim(Δ)$ определяется как наибольшая размерность любой из его граней или бесконечность, если нет конечной границы размерности граней.

Комплекс $Δ$ называется конечным, если он имеет конечное число граней или, что то же самое, если его множество вершин конечно. Кроме того, $Δ$ называется чистым, если оно конечномерно (но не обязательно конечно) и каждая грань имеет одинаковую размерность. Другими словами, $∆$ является чистым, если $dim(∆)$ конечен и каждая грань содержится в фасете размерности $dim(∆)$ .

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

Подкомплекс такой , ∆ $—$ это абстрактный симплициальный комплекс L что каждая грань L принадлежит $∆$ ; то есть $L \subseteq ∆$ и L — абстрактный симплициальный комплекс. Подкомплекс, состоящий из всех подмножеств одной грани $Δ,$ называют симплексом Δ $часто$ . (Однако некоторые авторы используют термин «симплекс» для лица или, довольно неоднозначно, как для лица, так и для подкомплекса, связанного с лицом, по аналогии с неабстрактной (геометрической) симплициальной комплексной терминологией. Во избежание двусмысленности мы не используйте в этой статье термин «симплекс» для лица в контексте абстрактных комплексов).

d - скелет ∆ $,$ — это подкомплекс $∆$ состоящий из всех граней $∆$ , размерность которых не превышает d . частности, 1-скелет называется основным графом Δ $В$ . 0-скелет графа $Δ$ можно отождествить с его множеством вершин, хотя формально это не совсем одно и то же (множество вершин представляет собой единое множество всех вершин, а 0-скелет представляет собой семейство одноэлементных множеств ).

Ссылка , грани $Y$ в $Δ$ , часто обозначаемая $Δ/ Y$ или $lk Δ (Y)$ , является подкомплексом $Δ$ определяемым формулой

\Delta /Y:=\{X\in \Delta \mid X\cap Y=\varnothing ,\,X\cup Y\in \Delta \}.

Обратите внимание, что связью пустого множества является $само Δ$ .

Симплициальные карты [ править ]

Учитывая два абстрактных симплициальных комплекса, $Δ$ и $Γ$ , симплициальное отображение — это функция $f$ , которая отображает вершины $Δ$ в вершины $Γ$ и которая обладает тем свойством, что для любой грани $из$ Δ $образ$ f ( $X X) является$ гранью Г. $$ Существует категория SCpx с абстрактными симплициальными комплексами в качестве объектов и симплициальными отображениями в качестве морфизмов . Это эквивалентно подходящей категории, определенной с использованием неабстрактных симплициальных комплексов .

Более того, категориальная точка зрения позволяет нам ужесточить связь между основным множеством S абстрактного симплициального комплекса $Δ$ и множеством вершин $V (Δ) \subseteq S$ комплекса $Δ$ : для целей определения категории абстрактных симплициальных комплексов элементы S , не лежащие в $V (Δ),$ не имеют значения. Точнее, SCpx эквивалентен категории, где:

объект — это множество S, снабженное набором непустых конечных подмножеств $∆$ , которое содержит все одиночные элементы и такое, что если $X$ находится в $∆$ и $Y \subseteq X$ непусто, то $Y$ также принадлежит $∆$ .
морфизм из $(S, Δ)$ в $(T, Γ)$ — это функция $f : S \to T$ такая, что образ любого элемента $Δ$ является элементом $Γ$ .

Геометрическая реализация [ править ]

мы можем сопоставить Любому абстрактному симплициальному комплексу (ASC) K топологическое пространство $|K|$ , называемое его геометрической реализацией . Существует несколько способов определения $|K|$ .

Геометрическое определение [ править ]

Каждый геометрический симплициальный комплекс (GSC) определяет ASC: ^[3]^: 14вершины ASC являются вершинами GSC, а грани ASC являются множествами вершин граней GSC. Например, рассмотрим GSC с 4 вершинами {1,2,3,4}, где максимальными гранями являются треугольник между {1,2,3} и линиями между {2,4} и {3,4}. Тогда соответствующий ASC содержит множества {1,2,3}, {2,4}, {3,4} и все их подмножества. Мы говорим, что GSC является геометрической реализацией ASC.

Каждая ИСК имеет геометрическую реализацию. Это легко увидеть для конечного ASC. ^[3]^: 14 Позволять $N:=|V(K)|$ . Определите вершины в $V(K)$ с вершинами ( N-1 )-мерного симплекса в $\mathbb {R} ^{N}$ . Построим GSC {conv(F): F — грань в K}. Очевидно, что ASC, связанный с этим GSC, идентичен K , поэтому мы действительно построили геометрическую реализацию K. Фактически, ASC можно реализовать, используя гораздо меньше измерений. Если АСЦ d -мерен (т. е. максимальная мощность симплекса в нем равна d +1), то он имеет геометрическую реализацию в $\mathbb {R} ^{2d+1}$ , но может не иметь геометрической реализации в $\mathbb {R} ^{2d}$ ^[3]^: 16 Особый случай d =1 соответствует известному факту, что любой график можно построить в виде $\mathbb {R} ^{3}$ где ребра представляют собой прямые линии, которые не пересекаются друг с другом, за исключением общих вершин, но не любой граф может быть построен в $\mathbb {R} ^{2}$ таким образом.

Если K — стандартный комбинаторный n -симплекс, то $|K|$ естественно отождествить с $∆ н$ .

Любые две геометрические реализации одной и той же АСК, даже в евклидовых пространствах разных размерностей, гомеоморфны . ^[3]^: 14 Поэтому, учитывая ИСК K, можно говорить о геометрической реализации K .

Топологическое определение

Строительство происходит следующим образом. Сначала определите $|K|$ как подмножество $[0,1]^{S}$ состоящий из функций $t\colon S\to [0,1]$ удовлетворяющее двум условиям:

\{s\in S:t_{s}>0\}\in K

\sum _{s\in S}t_{s}=1

Теперь представьте себе набор элементов $[0,1]^{S}$ с конечным носителем как прямой предел $[0,1]^{A}$ где A пробегает конечные подмножества S , и задайте этот прямой предел индуцированной топологии . Теперь дайте $|K|$ подпространства топология .

Категориальное определение [ править ]

Альтернативно, пусть ${\mathcal {K}}$ обозначают категорию, объектами которой являются грани $K$ и морфизмы которой являются включениями. Затем выберите общий порядок на множестве вершин $K$ и определите функтор F из ${\mathcal {K}}$ к категории топологических пространств следующим образом. Для любой грани X в K размерности n пусть $F (X) = ∆ н$ быть стандартным n -симплексом. Тогда порядок множества вершин определяет уникальную биекцию между элементами $X$ и вершинами $Δ. н$ , упорядоченный обычным образом $e 0 < e 1 < ... < e n$ . Если $Y \subseteq X$ — грань размерности $m < n$ , то эта биекция задает уникальную m -мерную грань $Δ. н$ . Определим $F (Y) \to (X) как$ единственное аффинное линейное вложение Δ $F м$ как это выдающееся лицо $Δ н$ , такое, что отображение вершин сохраняет порядок.

Затем мы можем определить геометрическую реализацию $|K|$ как копредел функтора F . Более конкретно $|K|$ является фактор-пространством дизъюнктного объединения

\coprod _{X\in K}{F(X)}

отношением эквивалентности которое отождествляет точку $y \in F (Y)$ с ее образом при отображении $F (Y) \to F (X)$ для каждого включения $Y \subseteq X.$ ,

Примеры [ править ]

1. Пусть V — конечное множество мощности $n + 1$ . Комбинаторный V n -симплекс с множеством вершин V представляет собой ASC, все грани которого являются непустыми подмножествами ( т. е. это степенное множество V ) . Если $V = S = {0, 1, ..., n},$ то этот АСЦ называется стандартным комбинаторным n -симплексом .

2. Пусть G — неориентированный граф. Кликовый комплекс G кликами — это ASC, все грани которого являются ( полными подграфами) G . G Комплекс независимости — это ASC, все грани которого являются независимыми множествами G ( это комплекс клики графа дополнений G). Кликовые комплексы являются типичным примером комплексов флагов . Комплекс флагов — это комплекс K, тем свойством, что каждое множество, все 2-элементные подмножества которого являются гранями K , само является гранью K. обладающий

3. Пусть H — гиперграф . Паросочетание , в котором в H — это набор ребер H каждые два ребра не пересекаются . Паросочетательный комплекс H — это ASC, все грани которого являются паросочетаниями в H . Это комплекс линейного графа H . независимости

4. Пусть P — частично упорядоченное множество (ЧУМ). Порядковый комплекс P собой — это ASC, все грани которого представляют цепи из P. конечные Его группы гомологий и другие топологические инварианты содержат важную информацию о частично упорядоченном P. множестве

5. Пусть M — метрическое пространство , а δ — действительное число. Комплекс Виеториса–Рипса — это ASC, грани которого являются конечными подмножествами M с диаметром не более δ . Он имеет приложения в теории гомологии , гиперболических группах , обработке изображений и мобильных одноранговых сетях . Это еще один пример комплекса флагов.

6. Пусть $I$ без квадратов быть мономиальным идеалом в кольце многочленов $S=K[x_{1},\dots ,x_{n}]$ (то есть идеал, порожденный произведениями подмножеств переменных). Тогда векторы экспонент этих бесквадратных мономов $S$ которых нет в $I$ определить абстрактный симплициальный комплекс с помощью карты $\mathbf {a} \in \{0,1\}^{n}\mapsto \{i\in [n]:a_{i}=1\}$ . Фактически, существует биекция между (непустыми) абстрактными симплициальными комплексами на $n$ вершинах и бесквадратными мономиальными идеалами в $S$ . Если $I_{\Delta }$ - идеал без квадратов, соответствующий симплициальному комплексу $\Delta$ тогда частное $S/I_{\Delta }$ известно как Стэнли–Рейснера кольцо ${\Delta }$ .

7. Для любого открытого покрытия C топологического пространства нервный комплекс C представляет собой абстрактный симплициальный комплекс , содержащий подсемейства C с непустым пересечением .

Перечисление [ править ]

Число абстрактных симплициальных комплексов на помеченных элементах (до n) (то есть на множестве S размера n ) на единицу меньше n- го числа Дедекинда . Эти числа растут очень быстро и известны только для $n \leq 9$ ; числа Дедекинда (начиная с n = 0):

1, 2, 5, 19, 167, 7580, 7828353, 2414682040997, 56130437228687557907787, 286386577668298411128469151667598498812365 (последовательность A01 4466 в OEIS ). Это соответствует количеству непустых антицепей подмножеств

n

множества.

Число абстрактных симплициальных комплексов, вершинами которых являются ровно n помеченных элементов, определяется последовательностью 696338374471993" (последовательность A006126 в OEIS ), начиная с n = 1 . Это соответствует числу антицепных покрытий меченого n -множества; существует явная биекция между антицепными покрытиями n -множества и симплициальными комплексами на n элементах, описываемыми в терминах их максимальных граней.

Количество абстрактных симплициальных комплексов ровно на n немаркированных элементах задается последовательностью «1, 2, 5, 20, 180, 16143, 489996795, 1392195548399980210» (последовательность A006602 в OEIS ), начиная с n = 1.

Вычислительные задачи [ править ]

Задача симплициального комплексного распознавания состоит в следующем: учитывая конечный ASC, решить, гомеоморфна ли его геометрическая реализация данному геометрическому объекту. Эта проблема неразрешима для любых d -мерных многообразий при d ≥ 5. ^[4]

Связь с другими понятиями [ править ]

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

ГИПЕРГРАФЫ = СЕМЕЙСТВА-МНОЖЕСТВА ⊃ СИСТЕМЫ НЕЗАВИСИМОСТИ = АБСТРАКТНО-СИМПЛИЦИАЛЬНЫЕ КОМПЛЕКСЫ ⊃ МАТРОИДЫ.

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

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

^ Ли, Джон М. , Введение в топологические многообразия, Springer 2011, ISBN 1-4419-7939-5 , стр. 153.
^ Корте, Бернхард ; Ловас, Ласло ; Шрейдер, Райнер (1991). Гридоиды . Спрингер Верлаг. п. 9. ISBN 3-540-18190-3 .
^ Перейти обратно: ^а ^б ^с ^д Матушек, Иржи (2007). Использование теоремы Борсука-Улама : Лекции по топологическим методам в комбинаторике и геометрии (2-е изд.). Берлин-Гейдельберг: Springer-Verlag. ISBN 978-3-540-00362-5 . Написано в сотрудничестве с Андерсом Бьёрнером и Гюнтером М. Циглером. , раздел 4.3
^ Стиллвелл, Джон (1993), Классическая топология и комбинаторная теория групп , Тексты для аспирантов по математике, том. 72, Спрингер, с. 247, ISBN 9780387979700 .

[Lee-1] Ли, Джон М. , Введение в топологические многообразия, Springer 2011, ISBN 1-4419-7939-5 , стр. 153.

[2] Корте, Бернхард ; Ловас, Ласло ; Шрейдер, Райнер (1991). Гридоиды . Спрингер Верлаг. п. 9. ISBN 3-540-18190-3 .

[:0-3] Перейти обратно: ^а ^б ^с ^д Матушек, Иржи (2007). Использование теоремы Борсука-Улама : Лекции по топологическим методам в комбинаторике и геометрии (2-е изд.). Берлин-Гейдельберг: Springer-Verlag. ISBN 978-3-540-00362-5 . Написано в сотрудничестве с Андерсом Бьёрнером и Гюнтером М. Циглером. , раздел 4.3

[4] Стиллвелл, Джон (1993), Классическая топология и комбинаторная теория групп , Тексты для аспирантов по математике, том. 72, Спрингер, с. 247, ISBN 9780387979700 .

[1]

[2]

[3]

[4]