Абстрактный симплициальный комплекс - Abstract simplicial complex - Wikipedia

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

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

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

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

Определения

Коллекция Δ непустых конечных подмножеств набор S называется набором-семейством.

Набор-семья Δ называется абстрактный симплициальный комплекс если для каждого набора Икс в Δ, и каждое непустое подмножество Y ⊆ Икс, набор Y также принадлежит Δ.

Конечные множества, принадлежащие Δ называются лица комплекса, и лицо Y Говорят, что принадлежит другому лицу Икс если Y ⊆ Икс, поэтому определение абстрактного симплициального комплекса может быть переформулировано следующим образом: каждая грань грани сложного Δ сам по себе лицо Δ. В набор вершин из Δ определяется как V(Δ) = ∪Δ, объединение всех граней Δ. Элементы множества вершин называются вершины комплекса. Для каждой вершины v из Δ, набор {v} - это грань комплекса, а каждая грань комплекса - конечное подмножество множества вершин.

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

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

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

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

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

В связь лица Y в Δ, часто обозначаемый Δ /Y или же lk_Δ(Y), является подкомплексом Δ определяется

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

Обратите внимание, что ссылка на пустой набор Δ сам.

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

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

• объект - это набор S снабженный набором непустых конечных подмножеств Δ содержащий все синглтоны и такой, что если Икс в Δ и Y ⊆ Икс непусто, то Y также принадлежит Δ.
• морфизм из (S, Δ) к (Т, Γ) это функция ж : S → Т такое, что изображение любого элемента Δ является элементом Γ.

Геометрическая реализация

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

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

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

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

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

В качестве альтернативы пусть ${\displaystyle {\mathcal {K}}}$ обозначают категорию, объектами которой являются грани K и чьи морфизмы являются включениями. Затем выберите общий заказ на множестве вершин K и определим функтор F из ${\displaystyle {\mathcal {K}}}$ в категорию топологических пространств следующим образом. Для любого лица Икс в K измерения п, позволять F(Икс) = Δ^п быть стандартом п-симплекс. Затем порядок в наборе вершин определяет уникальный биекция между элементами Икс и вершины Δ^п, заказывается обычным способом е₀ < е₁ < ... < е_п. Если Y ⊆ Икс это лицо измерения м < п, то эта биекция задает уникальный м-мерное лицо Δ^п. Определять F(Y) → F(Икс) быть уникальным аффинный линейный встраивание из Δ^м как это выдающееся лицо Δ^п, такое, что отображение на вершинах сохраняет порядок.

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

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

посредством отношение эквивалентности который определяет точку у ∈ F(Y) с изображением под картой F(Y) → F(Икс), для каждого включения Y ⊆ Икс.

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

Если K стандартный комбинаторный п-симплекс, то ${\displaystyle |K|}$ можно естественным образом отождествить с Δ^п.

Примеры

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

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

3. Пусть ЧАС быть гиперграф. А соответствие в ЧАС это набор ребер ЧАС, в котором каждые два ребра непересекающийся. В соответствующий комплекс ЧАС это ASC, все лица которого совпадения в ЧАС. Это комплекс независимости из линейный график из ЧАС.

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

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

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

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

Перечисление

Количество абстрактных симплициальных комплексов до п помеченные элементы (то есть на множестве S размера п) на единицу меньше, чем пth Число Дедекинда. Эти цифры растут очень быстро и известны только п ≤ 8; числа Дедекинда (начиная с п = 0):

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

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

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

Отношение к другим концепциям

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

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

Смотрите также

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

Рекомендации

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