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

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

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

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

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

Определения

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

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

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

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

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

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

Подкомплексом из А является абстрактным симплициальным комплексом L таким образом, что каждая грань L принадлежит к А ; то есть L ⊆ ∆ и 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 (∆) ⊆ S комплекса ∆ : для целей определения категории абстрактных симплициальных комплексов элементы S, не лежащие в V (Δ) , не имеют значения. Точнее, SCpx эквивалентен категории, в которой:

• объект - это множество S, снабженное набором непустых конечных подмножеств Δ, которое содержит все синглтоны и такое, что если X находится в Δ и Y ⊆ X непусто, то Y также принадлежит Δ .
• морфизм из ( S , ∆) в ( T , Γ) - это функция f  : S → 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}}$${\ displaystyle [0,1] ^ {A}}$${\ displaystyle | K |}$

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

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

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

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

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

Если K - стандартный комбинаторный n -симплекс, то его можно естественным образом отождествить с ∆ ⁿ . ${\ displaystyle | 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 . Если это бесквадратно идеал , соответствующий симплициальный комплекс , то фактор известен как Стенли-Райснер из . ${\ displaystyle I}$ ${\ Displaystyle S = К [x_ {1}, \ dots, x_ {n}]}$${\ displaystyle S}$${\ displaystyle I}$${\ displaystyle \ mathbf {a} \ in \ {0,1 \} ^ {n} \ mapsto \ {i \ in [n]: a_ {i} = 1 \}}$ ${\ displaystyle I _ {\ Delta}}$${\ displaystyle \ Delta}$ ${\ displaystyle S / I _ {\ Delta}}$${\ displaystyle {\ Delta}}$

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

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

Число абстрактных симплициальных комплексов на n помеченных элементах (то есть на множестве S размера n ) на единицу меньше n- го числа Дедекинда . Эти числа растут очень быстро и известны только для n ≤ 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.

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

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

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

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

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

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