Complejo simplicial abstracto

En combinatoria , un complejo simplicial abstracto (ASC), a menudo llamado complejo abstracto o simplemente complejo , es una familia de conjuntos que está cerrada bajo la toma de subconjuntos , es decir, cada 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 símplex abstracto se puede estudiar algebraicamente formando su anillo Stanley-Reisner ; esto establece una relación poderosa 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 en sí misma 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 cara) 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 caras que constan de dos elementos son unidimensionales, etc. La dimensión del complejo $dim(Δ)$ se define como la dimensión más grande de cualquiera de sus caras, o infinito si no hay un límite finito en 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. También se dice que $Δ$ es puro si tiene una dimensión finita (pero no necesariamente finito) y cada faceta tiene la misma dimensión. En otras palabras, $Δ$ es puro si $dim(Δ)$ es finito y cada cara está contenida en una faceta de dimensión $dim(Δ)$ .

Los complejos simpliciales abstractos unidimensionales son matemáticamente equivalentes a los grafos simples no dirigidos : el conjunto de vértices del complejo puede verse como el conjunto de vértices de un grafo, y las facetas de dos elementos del complejo corresponden a las aristas no dirigidas de un grafo. En 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 consiste en todos los subconjuntos de una sola cara de $Δ$ se denomina a menudo símplex de $Δ$ . (Sin embargo, algunos autores utilizan el término "símplex" para una cara o, de forma más bien ambigua, tanto para una cara como para el subcomplejo asociado con una cara, por analogía con la terminología de complejo simplicial no abstracto (geométrico) . Para evitar ambigüedades, no utilizamos en este artículo el término "símplex" para una cara en el contexto de complejos abstractos).

El d -esqueleto de $Δ$ es el subcomplejo de $Δ$ que consiste en todas las caras de $Δ$ que tienen dimensión como máximo d . En particular, el 1-esqueleto se denomina grafo subyacente de $Δ$ . El 0-esqueleto 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 0-esqueleto 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\en \Delta \mid X\cap Y=\varnothing ,\,X\cup Y\en \Delta \}.

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

Mapas simpliales

Dados dos complejos simpliciales abstractos, $Δ$ y $Γ$ , una funció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 funciones 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 los efectos de definir una categoría de complejos simpliciales abstractos, los elementos de S que no se encuentran en $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 singletons y tal que si $X$ está en $Δ$ e $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 (ACE) K un espacio topológico , llamado su realización geométrica . Existen varias formas de definir . ${\estilo de visualización |K|}$ ${\estilo de visualización |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, considérese 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 . Identifique los vértices en con los vértices de un símplex de ( N-1 )-dimensional en . Construya 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 se puede realizar usando muchas menos dimensiones. Si un ASC es d -dimensional (es decir, la cardinalidad máxima de un símplex en él es d +1), entonces tiene una realización geométrica en , pero podría no tener una realización geométrica en ^[3]^{: 16} El caso especial d = 1 corresponde al hecho bien conocido de que cualquier grafo puede trazarse en donde los bordes son líneas rectas que no se intersecan entre sí excepto en vértices comunes, pero no cualquier grafo puede trazarse en de esta manera. $N:=|V(K)|$ ${\estilo de visualización V(K)}$ $\mathbb {R} ^{N}$ $\mathbb {R} ^{2d+1}$ $\mathbb {R} ^{2d}$ $\mathbb {R} ^{3}$ $\mathbb {R} ^{2}$

Si K es el n -símplex combinatorio estándar, entonces puede identificarse naturalmente con $Δ$ $n$ . ${\estilo de visualización |K|}$

Toda realización geométrica de un mismo ASC, incluso en espacios euclidianos de diferentes dimensiones, es homeomorfa . ^[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 es la siguiente. Primero, se define como un subconjunto de funciones que satisfacen las dos condiciones: ${\estilo de visualización |K|}$ $[0,1]^{S}$ $t\colon S\to [0,1]$

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

\suma_{s\in} S}t_{s}=1

Ahora piense en el conjunto de elementos de con soporte finito como el límite directo de donde A se extiende sobre subconjuntos finitos de S , y dé a ese límite directo la topología inducida . Ahora dé la topología del subespacio . $[0,1]^{S}$ $[0,1]^{A}$ ${\estilo de visualización |K|}$

Definición categórica

Alternativamente, 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 funtor F de 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 habitual $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$ . Definamos $F$ $($ $Y$ $) \to$ $F$ $($ $X$ $)$ como la incrustación lineal afín única de $Δ$ $m$ como esa cara distinguida de $Δ$ $n$ , tal que la función en los vértices preserva el orden. ${\mathcal {K}}$ ${\mathcal {K}}$

Podemos entonces definir la realización geométrica como el colimite del funtor F . Más específicamente es el espacio cociente de la unión disjunta ${\estilo de visualización |K|}$ ${\estilo de visualización |K|}$

\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 función $F (Y) \to F (X)$ , para cada inclusión $Y \subseteq X$ .

Ejemplos

1. Sea V un conjunto finito de cardinalidad $n + 1$ . El n -símplex combinatorio con el 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 llama n -símplex combinatorio estándar .

2. Sea G un grafo no dirigido. El complejo clique de G es un ASC cuyas caras son todas las cliques (subgrafos completos) de G . El complejo de independencia de G es un ASC cuyas caras son todas los conjuntos independientes de G (es el complejo clique del grafo complementario de G). Los complejos clique son el ejemplo prototípico de los complejos bandera . Un complejo bandera es un complejo K con la propiedad de que cada conjunto, todos cuyos subconjuntos de 2 elementos son caras de K , es en sí mismo una cara de K .

3. Sea H un hipergrafo . Un emparejamiento en H es un conjunto de aristas de H , en el que cada dos aristas son disjuntas . El complejo de emparejamiento de H es un ASC cuyas caras son todas emparejamientos en H. Es el complejo de independencia del grafo lineal 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 complejo de banderas cuyas caras son los subconjuntos finitos de M con un diámetro como máximo de δ . Tiene aplicaciones en teoría de homología , grupos hiperbólicos , procesamiento de imágenes y redes móviles ad hoc . Es otro ejemplo de complejo de banderas.

6. Sea un ideal monomial sin cuadrados en un anillo polinomial (es decir, un ideal generado por productos de subconjuntos de variables). Entonces los vectores exponenciales de esos monomios sin cuadrados de que no están en determinan un complejo simplicial abstracto mediante la función . De hecho, existe una biyección entre complejos simpliciales abstractos (no vacíos) en $n$ vértices e ideales monomiales sin cuadrados en $S$ . Si es el ideal sin cuadrados correspondiente al complejo simplicial , entonces el cociente se conoce como anillo Stanley-Reisner de . $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. 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 simples abstractos en hasta n elementos etiquetados (es decir, en 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 se conocen solo 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 la 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 está 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 cubiertas anticadena de un conjunto n etiquetado ; hay una clara biyección entre las cubiertas anticadena de un conjunto n 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 está 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 es: 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-CONJUNTOS ⊃ SISTEMAS-INDEPENDENCIA = COMPLEJOS-ABSTRACTOS-SIMPLICIALES ⊃ 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.
^ abcd 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-5. Escrito 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 de grupos combinatorios, Textos de posgrado en matemáticas, vol. 72, Springer, pág. 247, ISBN 9780387979700.