complejo simplicial abstracto

En combinatoria , un complejo simplicial abstracto (CSA), a menudo llamado complejo abstracto o simplemente complejo , es una familia de conjuntos cerrada bajo la operación de tomar subconjuntos , es decir, todo subconjunto de un conjunto en la familia también está en la familia. Es una descripción puramente combinatoria de la noción geométrica de un complejo simplicial . ^{[ 1 ]} Por ejemplo, en un complejo simplicial bidimensional, los conjuntos en la familia son los triángulos (conjuntos de tamaño 3), sus aristas (conjuntos de tamaño 2) y sus vértices (conjuntos de tamaño 1).

En el contexto de los matroides y los greedoides , los complejos simpliciales abstractos también se denominan sistemas de independencia . ^{[ 2 ]}

Un simplex abstracto puede estudiarse algebraicamente formando su anillo de Stanley-Reisner ; esto establece una poderosa relación entre la combinatoria y el álgebra conmutativa .

Definiciones

Una colección $Δ$ de subconjuntos finitos no vacíos de un conjunto S se denomina familia de conjuntos.

Una familia de conjuntos $Δ$ se denomina complejo simplicial abstracto si, para cada conjunto $X$ en $Δ$ y cada subconjunto no vacío $Y \subseteq X$ , el conjunto $Y$ también pertenece a $Δ$ .

Los conjuntos finitos que pertenecen a $Δ$ se denominan caras del complejo, y se dice que una cara $Y pertenece a otra cara$ $X$ si $Y \subseteq X$ , por lo que la definición de un complejo simplicial abstracto puede reformularse diciendo que cada cara de una cara de un complejo $Δ$ es a su vez una cara de $Δ$ . El conjunto de vértices de $Δ$ se define como $V (Δ) = \cupΔ$ , la unión de todas las caras de $Δ$ . Los elementos del conjunto de vértices se denominan vértices del complejo. Para cada vértice v de $Δ$ , el conjunto { v } es una cara del complejo, y cada cara del complejo es un subconjunto finito del conjunto de vértices.

Las caras máximas de $Δ$ (es decir, las caras que no son subconjuntos de ninguna otra) se denominan facetas del complejo. La dimensión de una cara $X$ en $Δ$ se define como $dim(X) = | X | - 1$ : las caras que constan de un solo elemento son de dimensión cero, las que constan de dos elementos son de dimensión uno, etc. La dimensión del complejo $dim(Δ)$ se define como la mayor dimensión de cualquiera de sus caras, o infinito si no existe un límite finito para la dimensión de las caras.

Se dice que el complejo $Δ$ es finito si tiene un número finito de caras, o equivalentemente si su conjunto de vértices es finito. Además, se dice que $Δ$ es puro si es de dimensión finita (aunque no necesariamente finita) y cada cara tiene la misma dimensión. En otras palabras, $Δ$ es puro si $dim(Δ)$ es finito y cada cara está contenida en una cara de dimensión $dim(Δ)$ .

Los complejos simpliciales abstractos unidimensionales son matemáticamente equivalentes a grafos simples no dirigidos : el conjunto de vértices del complejo puede considerarse como el conjunto de vértices de un grafo, y las facetas de dos elementos del complejo corresponden a aristas no dirigidas de un grafo. Desde esta perspectiva, las facetas de un elemento de un complejo corresponden a vértices aislados que no tienen aristas incidentes.

Un subcomplejo de $Δ$ es un complejo simplicial abstracto L tal que cada cara de L pertenece a $Δ$ ; es decir, $L \subseteq Δ$ y L es un complejo simplicial abstracto. Un subcomplejo que consta de todos los subconjuntos de una sola cara de $Δ$ se suele llamar simplex de $Δ$ . (Sin embargo, algunos autores utilizan el término "símplex" para referirse a una cara o, de forma bastante ambigua, tanto para una cara como para el subcomplejo asociado a ella, por analogía con la terminología de los complejos simpliciales no abstractos (geométricos) . Para evitar ambigüedad, en este artículo no utilizamos el término "símplex" para referirnos a una cara en el contexto de los complejos abstractos).

El esqueleto d de $Δ$ es el subcomplejo de $Δ$ que consta de todas las caras de $Δ$ que tienen dimensión como máximo d . En particular, el esqueleto 1 se denomina grafo subyacente de $Δ$ . El esqueleto 0 de $Δ$ se puede identificar con su conjunto de vértices, aunque formalmente no es exactamente lo mismo (el conjunto de vértices es un único conjunto de todos los vértices, mientras que el esqueleto 0 es una familia de conjuntos de un solo elemento).

El enlace de una cara $Y$ en $Δ$ , a menudo denotado $Δ/ Y$ o $lk Δ (Y)$ , es el subcomplejo de $Δ$ definido por

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

Nótese que el enlace del conjunto vacío es $Δ$ mismo.

mapas simpliciales

Dados dos complejos simpliciales abstractos, $Δ$ y $Γ$ , una aplicación simplicial es una función $f$ que asigna los vértices de $Δ$ a los vértices de $Γ$ y que tiene la propiedad de que para cualquier cara $X$ de $Δ$ , la imagen $f$ $($ $X$ $)$ es una cara de $Γ$ . Existe una categoría SCpx con complejos simpliciales abstractos como objetos y aplicaciones simpliciales como morfismos . Esto es equivalente a una categoría adecuada definida utilizando complejos simpliciales no abstractos .

Además, el punto de vista categórico nos permite estrechar la relación entre el conjunto subyacente S de un complejo simplicial abstracto $Δ$ y el conjunto de vértices $V (Δ) \subseteq S$ de $Δ$ : a efectos de definir una categoría de complejos simpliciales abstractos, los elementos de S que no pertenecen a $V (Δ)$ son irrelevantes. Más precisamente, SCpx es equivalente a la categoría donde:

Un objeto es un conjunto S equipado con una colección de subconjuntos finitos no vacíos $Δ$ que contiene todos los elementos unitarios y tal que si $X$ está en $Δ$ y $Y \subseteq X$ no está vacío, entonces $Y$ también pertenece a $Δ$ .
Un morfismo de $(S, Δ)$ a $(T, Γ)$ es una función $f : S \to T$ tal que la imagen de cualquier elemento de $Δ$ es un elemento de $Γ$ .

Realización geométrica

Podemos asociar a cualquier complejo simplicial abstracto (CSA) K un espacio topológico $|K|$ , llamada su realización geométrica . Hay varias maneras de definir $|K|$ .

Definición geométrica

Todo complejo simplicial geométrico (CSG) determina un ASC: ^{[ 3 ]}^{: 14} los vértices del ASC son los vértices del CSG, y las caras del ASC son los conjuntos de vértices de las caras del CSG. Por ejemplo, consideremos un CSG con 4 vértices {1,2,3,4}, donde las caras máximas son el triángulo entre {1,2,3} y las líneas entre {2,4} y {3,4}. Entonces, el ASC correspondiente contiene los conjuntos {1,2,3}, {2,4}, {3,4} y todos sus subconjuntos. Decimos que el CSG es la realización geométrica del ASC.

Cada ASC tiene una realización geométrica. Esto es fácil de ver para un ASC finito. ^{[ 3 ]}^{: 14} Sea $N:=|V(K)|$ . Identifique los vértices en $V(K)$ con los vértices de un simplex ( N − 1)-dimensional en $\mathbb {R} ^{N}$ . Construimos el GSC { conv (F): F es una cara en K}. Claramente, el ASC asociado con este GSC es idéntico a K , por lo que de hecho hemos construido una realización geométrica de K. De hecho, un ASC puede realizarse usando muchas menos dimensiones. Si un ASC es d -dimensional (es decir, la cardinalidad máxima de un simplex en él es d +1), entonces tiene una realización geométrica en $\mathbb {R} ^{2d+1}$ , pero podría no tener una realización geométrica en $\mathbb {R} ^{2d}$ ^{[ 3 ]}^{: 16} El caso especiald=1 corresponde al hecho bien conocido de que cualquiergráficopuede ser trazado en $\mathbb {R} ^{3}$ donde los bordes son líneas rectas que no se intersecan entre sí excepto en vértices comunes, pero no se puede trazar cualquier gráfico en $\mathbb {R} ^{2}$ de este modo.

Si K es el n -símplex combinatorio estándar , entonces $|K|$ puede identificarse naturalmente con $Δ n$ .

Cada dos realizaciones geométricas del mismo ASC, incluso en espacios euclidianos de diferentes dimensiones, son homeomorfas . ^{[ 3 ]}^{: 14} Por lo tanto, dado un ASC K, se puede hablar de la realización geométrica de K.

Definición topológica

La construcción se realiza de la siguiente manera. Primero, defina $|K|$ como un subconjunto de $[0,1]^{S}$ que consta de funciones $t\colon S\to [0,1]$ que cumplen las dos condiciones:

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

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

Ahora piensa en el conjunto de elementos de $[0,1]^{S}$ con soporte finito como límite directo de $[0,1]^{A}$ donde A recorre subconjuntos finitos de S , y ese límite directo da la topología inducida . Ahora da $|K|$ la topología del subespacio .

Definición categórica

Alternativamente, deje ${\mathcal {K}}$ Denotemos la categoría cuyos objetos son las caras de $K$ y cuyos morfismos son inclusiones. A continuación, elijamos un orden total en el conjunto de vértices de $K$ y definamos un functor F a partir de ${\mathcal {K}}$ a la categoría de espacios topológicos de la siguiente manera. Para cualquier cara X en K de dimensión n , sea $F (X) = Δ n$ el n -símplex estándar . El orden en el conjunto de vértices especifica entonces una biyección única entre los elementos de $X$ y los vértices de $Δ n$ , ordenados de la forma usual $e 0 < e 1 < ... < e n$ . Si $Y \subseteq X$ es una cara de dimensión $m < n$ , entonces esta biyección especifica una cara m -dimensional única de $Δ n$ . Definimos $F (Y) \to F (X)$ como la incrustación lineal afín única de $Δ$ $m$ como esa cara distinguida de $Δ$ $n$ , tal que el mapeo en los vértices es preservador del orden.

Entonces podemos definir la realización geométrica $|K|$ como colímite del functor F. Más específicamente $|K|$ es el espacio cociente de la unión disjunta

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

por la relación de equivalencia que identifica un punto $y \in F (Y)$ con su imagen bajo la aplicación $F (Y) \to F (X)$ , para toda inclusión $Y \subseteq X$ .

Ejemplos

1. Sea V un conjunto finito de cardinalidad $n + 1.$ El n- símplex combinatorio con conjunto de vértices V es un ASC cuyas caras son todas subconjuntos no vacíos de V (es decir, es el conjunto potencia de V ). Si $V = S = {0, 1, ..., n},$ entonces este ASC se denomina n- símplex combinatorio estándar .

2. Sea G un grafo no dirigido. El complejo de cliques de G es un ASC cuyas caras son todos cliques (subgrafos completos) de G. El complejo de independencia de G es un ASC cuyas caras son todos conjuntos independientes de G (es el complejo de cliques del grafo complemento de G). Los complejos de cliques son el ejemplo prototípico de complejos de banderas . Un complejo de banderas es un complejo K con la propiedad de que todo conjunto, cuyos subconjuntos de 2 elementos son caras de K , es a su vez una cara de K.

3. Sea H un hipergrafo . Un emparejamiento en H es un conjunto de aristas de H , en el que cada par de aristas es disjunto . El complejo de emparejamiento de H es un ASC cuyas caras son todos emparejamientos en H. Es el complejo de independencia del grafo de líneas de H.

4. Sea P un conjunto parcialmente ordenado (poset). El complejo de orden de P es un ASC cuyas caras son todas cadenas finitas en P. Sus grupos de homología y otros invariantes topológicos contienen información importante sobre el poset P.

5. Sea M un espacio métrico y δ un número real. El complejo de Vietoris-Rips es un ASC cuyas caras son los subconjuntos finitos de M con diámetro como máximo δ . Tiene aplicaciones en la teoría de la homología , los grupos hiperbólicos , el procesamiento de imágenes y las redes móviles ad hoc . Es otro ejemplo de un complejo de banderas.

6. Deja $I$ sea un ideal monomial libre de cuadrados en un anillo polinomial $S=K[x_{1},\dots ,x_{n}]$ (es decir, un ideal generado por productos de subconjuntos de variables). Entonces, los vectores exponenciales de esos monomios libres de cuadrados de $S$ que no están en $I$ determinar un complejo simplicial abstracto a través del mapa $\mathbf {a} \in \{0,1\}^{n}\mapsto \{i\in [n]:a_{i}=1\}$ . De hecho, existe una biyección entre complejos simpliciales abstractos (no vacíos) con $n$ vértices e ideales monomiales libres de cuadrados en $S$ . Si $I_{\Delta }$ es el ideal libre de cuadrados correspondiente al complejo simplicial $\Delta$ entonces el cociente $S/I_{\Delta }$ se conoce como el anillo Stanley-Reisner de ${\Delta }$ .

7. Para cualquier recubrimiento abierto C de un espacio topológico, el complejo nervioso de C es un complejo simplicial abstracto que contiene las subfamilias de C con una intersección no vacía .

Enumeración

El número de complejos simpliciales abstractos sobre hasta n elementos etiquetados (es decir, sobre un conjunto S de tamaño n ) es uno menos que el n -ésimo número de Dedekind . Estos números crecen muy rápidamente y solo se conocen para $n \leq 9$ ; los números de Dedekind son (comenzando con n = 0):

1, 2, 5, 19, 167, 7580, 7828353, 2414682040997, 56130437228687557907787, 286386577668298411128469151667598498812365 (secuencia A014466 en el OEIS ) . Esto corresponde al número de anticadenas no vacías de subconjuntos de un conjunto

n

.

El número de complejos simpliciales abstractos cuyos vértices son exactamente n elementos etiquetados viene dado por la secuencia "1, 2, 9, 114, 6894, 7785062, 2414627396434, 56130437209370320359966, 286386577668298410623295216696338374471993" (secuencia A006126 en la OEIS ) , comenzando en n = 1. Esto corresponde al número de recubrimientos de anticadenas de un n -conjunto etiquetado; existe una clara biyección entre los recubrimientos de anticadenas de un n -conjunto y los complejos simpliciales en n elementos descritos en términos de sus caras máximas.

El número de complejos simpliciales abstractos en exactamente n elementos no etiquetados viene dado por la secuencia "1, 2, 5, 20, 180, 16143, 489996795, 1392195548399980210" (secuencia A006602 en la OEIS ) , comenzando en n = 1.

Problemas computacionales

El problema de reconocimiento de complejos simpliciales consiste en: dado un ASC finito, decidir si su realización geométrica es homeomorfa a un objeto geométrico dado. Este problema es indecidible para cualquier variedad d -dimensional para d ≥ 5. ^{[ 4 ]}

Relación con otros conceptos

Un complejo simplicial abstracto con una propiedad adicional llamada propiedad de aumento o propiedad de intercambio produce un matroide . La siguiente expresión muestra las relaciones entre los términos:

HIPERGRAFOS = FAMILIAS DE CONJUNTOS ⊃ SISTEMAS DE INDEPENDENCIA = COMPLEJOS SIMPLICIALES ABSTRACTOS ⊃ MATROIDES.

Véase también

Referencias

↑ Lee, John M. , Introducción a las variedades topológicas, Springer 2011, ISBN 1-4419-7939-5, pág. 153
↑ Korte, Bernhard ; Lovász, László ; Schrader, Rainer (1991). Codiciosos . Springer-Verlag. pag. 9.ISBN 3-540-18190-3.
1 2 3 4 Matoušek, Jiří (2007). Uso del teorema de Borsuk-Ulam : Lecciones sobre métodos topológicos en combinatoria y geometría (2.ª ed.). Berlín-Heidelberg: Springer-Verlag. ISBN 978-3-540-00362-5Escrito en colaboración con Anders Björner y Günter M. Ziegler ., Sección 4.3
↑ Stillwell, John (1993), Topología clásica y teoría combinatoria de grupos , Textos de posgrado en matemáticas, vol. 72, Springer, pág. 247, ISBN 9780387979700.

[Lee-1] Lee, John M. , Introducción a las variedades topológicas, Springer 2011, ISBN 1-4419-7939-5, pág. 153

[2] Korte, Bernhard ; Lovász, László ; Schrader, Rainer (1991). Codiciosos . Springer-Verlag. pag. 9.ISBN 3-540-18190-3.

[:0-3] 1 2 3 4 Matoušek, Jiří (2007). Uso del teorema de Borsuk-Ulam : Lecciones sobre métodos topológicos en combinatoria y geometría (2.ª ed.). Berlín-Heidelberg: Springer-Verlag. ISBN 978-3-540-00362-5Escrito en colaboración con Anders Björner y Günter M. Ziegler ., Sección 4.3

[4] Stillwell, John (1993), Topología clásica y teoría combinatoria de grupos , Textos de posgrado en matemáticas, vol. 72, Springer, pág. 247, ISBN 9780387979700.

[ 1 ]

[ 2 ]

[ 4 ]