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

Геометрическое представление абстрактного симплициального комплекса, который не является действительным симплициальным комплексом .

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

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

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

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

Набор $∆$ непустых конечных подмножеств множества S называется множеством-семейством.

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

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

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

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

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

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

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

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

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

Обратите внимание, что звено пустого множества - это само $Δ$ .

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

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

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

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

Мы можем сопоставить абстрактный симплициальный комплекс K топологическое пространство , называется его геометрическая реализацией , которая является носителем симплициального комплекса . Построение происходит следующим образом. ${\ displaystyle | K |}$

Во-первых, определите как подмножество, состоящее из функций, удовлетворяющих двум условиям: ${\ displaystyle | K |}$ ${\ displaystyle [0,1] ^ {S}}$ ${\ Displaystyle т \ двоеточие S \ к [0,1]}$

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

{\ Displaystyle \ сумма _ {s \ in S} t_ {s} = 1}

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

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

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

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

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

Если K конечно, то мы можем описать более просто. Выберите вложение множества вершин K в качестве аффинно независимого подмножества некоторого евклидова пространства достаточно большой размерности N . Тогда любую грань X в K можно отождествить с геометрическим симплексом in, натянутым на соответствующие вложенные вершины. Возьмем объединение всех таких симплексов. $|K|$ $\mathbb {R} ^{N}$ $\mathbb {R} ^{N}$ $|K|$

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

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

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

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

3. Пусть H - гиперграф . Соответствия в H представляет собой множество ребер Н , в которых каждые два ребра не пересекаются . Соответствующий комплекс Н является АСК, грани которого являются все паросочетания в H . Это комплексная независимость от линейного графика в H .

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

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

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

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

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

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

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

n

множества.

Число абстрактных симплициальных комплексов, вершинами которых являются ровно n помеченных элементов, задается последовательностью «1, 2, 9, 114, 6894, 7785062, 2414627396434, 56130437209370320359966» (последовательность A006126 в OEIS ), начиная с n = 1. Это соответствует количеству антицепных покрытий помеченного n -множества; существует явная биекция между антицепными покрытиями n -множества и симплициальными комплексами на n элементах, описанными в терминах их максимальных граней.

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

Отношение к другим концепциям [ править ]

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

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

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

Теорема Крускала – Катоны
Симплициальный набор

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

^ Ли, Джон М. , Введение в топологические многообразия, Springer 2011, ISBN 1-4419-7939-5 , p153
^ Корте, Бернхард ; Ловас, Ласло ; Шредер, Райнер (1991). Гридоиды . Springer-Verlag. п. 9. ISBN 3-540-18190-3.

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

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

[1]