Complejo simple abstracto

En combinatoria , un complejo simplicial abstracto (ASC), a menudo llamado complejo abstracto o simplemente complejo , es una familia de conjuntos que está cerrada al tomar 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 complejo simplicial . ^[1] Por ejemplo, en un complejo simplicial bidimensional, los conjuntos de 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 matroides y codiciosos , los complejos simpliciales abstractos también se denominan sistemas de independencia . ^[2]

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

Definiciones

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

Una familia de conjuntos $Δ$ se llama 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 llaman 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 se puede reformular diciendo que cada cara de una cara de un complejo $Δ$ es en sí mismo 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, 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 $tenue(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 el infinito si no hay 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 de manera equivalente si su conjunto de vértices es finito. Además, se dice que $Δ$ es puro si es de dimensión finita (pero no necesariamente finita) 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 gráficos simples no dirigidos : el conjunto de vértices del complejo puede verse como el conjunto de vértices de un gráfico, y las facetas de dos elementos del complejo corresponden a bordes no dirigidos de un gráfico. En esta vista, 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 $Δ$ a menudo se denomina simplex de $Δ$ . (Sin embargo, algunos autores utilizan el término "símplejo" para una cara o, de manera bastante ambigua, tanto para una cara como para el subcomplejo asociado con una cara, por analogía con la terminología compleja simplicial no abstracta (geométrica) . Para evitar ambigüedades, no utilice 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 consta de todas las caras de $Δ$ que tienen dimensión como máximo d . En particular, el 1-esqueleto se llama gráfico 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 conjunto único de todos los vértices, mientras que el esqueleto 0 es una familia de conjuntos de un solo elemento ).

El vínculo 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 \}.

Tenga en cuenta que el enlace del conjunto vacío es el propio $Δ$ .

Mapas simples

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 $Γ$ . Hay una categoría SCpx con complejos simpliciales abstractos como objetos y mapas simpliciales como morfismos . Esto equivale 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, el 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 singleton 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 (ASC) K un espacio topológico , llamado su realización geométrica . Hay varias formas de definirlo . $|K|$ $|K|$

Definición geométrica

Todo complejo geométrico simplicial (GSC) determina un ASC: ^[3]^{: 14} los vértices del ASC son los vértices del GSC, y las caras del ASC son los conjuntos de vértices de las caras del GSC. Por ejemplo, considere un GSC 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 GSC 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 ( 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 efectivamente 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 simplex 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 se puede trazar cualquier gráfico donde las aristas sean líneas rectas que no se cruzan entre sí excepto en los vértices comunes, pero ningún gráfico se puede trazar de esta manera. $N:=|V(K)|$ $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$ . $|K|$

Cada dos realizaciones geométricas de un 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 es la siguiente. Primero, defina como un subconjunto de funciones que satisfacen las dos condiciones: $|K|$ $[0,1]^{S}$ $t\dos puntos S\to [0,1]$

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

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

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

Definición categórica

Alternativamente, denotemos la categoría cuyos objetos son las caras de $K$ y cuyos morfismos son inclusiones. Luego elija un orden total en el conjunto de vértices de $K$ y defina un funtor F desde 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 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$ . Defina $F$ $($ $Y$ $) \to$ $F$ $($ $X$ $)$ como la incrustación lineal afín única de $Δ$ $m$ como esa cara distinguida de $Δ$ $n$ , de modo que el mapa en los vértices preserva el orden. ${\mathcal {K}}$ ${\mathcal {K}}$

Entonces podemos definir la realización geométrica como el colímite del funtor F. Más específicamente es el espacio cociente de la unión disjunta $|K|$ $|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 el mapa $F (Y) \to F (X)$ , para cada inclusión $Y \subseteq X$ .

Ejemplos

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

2. Sea G un gráfico no dirigido. El complejo de camarilla de G es un ASC cuyas caras son todas camarillas (subgrafos completos) de G. El complejo de independencia de G es un ASC cuyas caras son todas conjuntos independientes de G (es el complejo de camarilla del gráfico complementario de G). Los complejos de camarilla son el ejemplo prototípico de complejos de banderas . Un complejo de 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 . Una coincidencia en H es un conjunto de aristas de H , en las que cada dos aristas son disjuntas . El complejo coincidente de H es un ASC cuyas caras son todas coincidentes en H. Es el complejo de independencia del gráfico 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 otras invariantes topológicas contienen información importante sobre el poset P.

5. Sea M un espacio métrico y δ un número real. El complejo Vietoris-Rips es un ASC cuyas caras son los subconjuntos finitos de M con un diámetro como máximo δ . 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 monomio sin cuadrados en un anillo polinómico (es decir, un ideal generado por productos de subconjuntos de variables). Luego, los vectores exponentes de esos monomios libres de cuadrados que no están en determinan un complejo simplicial abstracto a través del mapa . De hecho, existe una biyección entre complejos simpliciales abstractos (no vacíos) en n $vértices$ e ideales monomios libres de cuadrados en $S.$ Si es el ideal sin cuadrados correspondiente al complejo simplicial, entonces el cociente se conoce como anillo de 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\}$ ${\ Displaystyle I _ {\ Delta}}$ $\Delta$ $S/I_{\Delta}$ ${\Delta }$

7. Para cualquier cubierta abierta 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 en hasta n elementos etiquetados (es decir, en un conjunto S de tamaño n ) es uno menos que el enésimo número de Dedekind . Estos números crecen muy rápidamente y sólo 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 A014 466 en la OEIS ). Esto corresponde al número de anticadenas no vacías de subconjuntos de un

n

conjunto.

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, 28638657766829841062329521669 6338374471993" (secuencia A006126 en el OEIS ), comenzando en n = 1 Esto corresponde al número de cubiertas anticadena de un conjunto n etiquetado ; existe una clara biyección entre cubiertas anticadena de un n -conjunto y 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 sin etiquetar viene dado por la secuencia "1, 2, 5, 20, 180, 16143, 489996795, 1392195548399980210" (secuencia A006602 en el OEIS ), comenzando en n = 1.

Problemas computacionales

El problema de reconocimiento complejo simple es: dado un ASC finito, decidir si su realización geométrica es homeomórfica con respecto a un objeto geométrico dado. Este problema es indecidible para cualquier variedad d -dimensional para d ≥ 5.

Relación con otros conceptos

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

HIPERGRAFÍAS = CONJUNTOS-FAMILIAS ⊃ SISTEMAS-INDEPENDENCIA = COMPLEJOS-ABSTRACTOS-SIMPLICIALES ⊃ MATROIDES.

Ver también

Referencias

^ Lee, John M. , Introducción a las variedades topológicas, Springer 2011, ISBN 1-4419-7939-5 , p153
^ 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 : conferencias 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