Los complejos de pandillas , los complejos de banderas y los hipergráficos conformes son objetos matemáticos estrechamente relacionados en la teoría de grafos y la topología geométrica, cada uno de los cuales describe las pandillas (subgrafos completos) de un gráfico no dirigido .
El complejo clique X ( G ) de un grafo no dirigido G es un extracto simplicial complejo (es decir, una familia de conjuntos finitos cerrada bajo la operación de tomar subconjuntos), formado por los conjuntos de vértices en las camarillas de G . Cualquier subconjunto de una camarilla es en sí mismo una camarilla, por lo que esta familia de conjuntos cumple con el requisito de un complejo simplicial abstracto de que cada subconjunto de un conjunto en la familia también debe estar en la familia. El complejo clique también se puede ver como un espacio topológico en el que cada clique de k vértices está representado por un simplex de dimensión k - 1. El esqueleto 1 de X ( G ) (también conocido como el gráfico subyacente del complejo) es un gráfico no dirigido con un vértice para cada conjunto de 1 elemento de la familia y un borde para cada conjunto de 2 elementos de la familia; es isomorfo a G . [1]
Los complejos de camarilla también se conocen como complejos de Whitney , en honor a Hassler Whitney . Una triangulación de Whitney o una triangulación limpia de una variedad bidimensional es una incrustación de un gráfico G en la variedad de tal manera que cada cara es un triángulo y cada triángulo es una cara. Si una gráfica G tiene una triangulación Whitney, debe formar un complejo de célula que es isomorfo al complejo Whitney de G . En este caso, el complejo (visto como un espacio topológico) es homeomorfo a la variedad subyacente. Un gráfico G tiene un complejo de clique de 2 variedades y se puede incrustar como una triangulación de Whitney, si y solo si G es localmente cíclico ; esto significa que, para cada vértice v en el gráfico, el subgrafo inducido formado por los vecinos de v forma un solo ciclo. [2]
El complejo clique de G es equivalente a la independencia complejo del grafo complemento de G .
Complejo de banderas
Un complejo de banderas es un complejo simplicial abstracto de modo que cada conjunto de vértices en el que todos los pares son caras del complejo es también en sí mismo una cara del complejo. Por lo tanto, los complejos de bandera y los complejos de camarilla son esencialmente lo mismo. Cualquier complejo de bandera es el complejo de camarilla de su 1-esqueleto. Sin embargo, en muchos casos es conveniente definir un complejo de banderas directamente a partir de algunos datos distintos de un gráfico, en lugar de hacerlo indirectamente como el complejo de pandillas de un gráfico derivado de esos datos. [3]
Mikhail Gromov definió la condición de no-Δ como la condición de ser un complejo de banderas.
Hipergrafo conformal
El gráfico primario G ( H ) de un hipergráfico es el gráfico del mismo conjunto de vértices que tiene como aristas los pares de vértices que aparecen juntos en el mismo hipergrabado . Se dice que un hipergrafo es conforme si cada pandilla máxima de su grafo primario es un hipergrafia, o de manera equivalente, si cada camarilla de su grafo primario está contenida en algún hiperegrafismo. [4] Si se requiere que el hipergráfico esté cerrado hacia abajo (por lo que contiene todas las hipergrafias que están contenidas en alguna hipergrafia), entonces el hipergrafo es conforme precisamente cuando es un complejo de banderas. Esto relaciona el lenguaje de los hipergráficos con el lenguaje de los complejos simpliciales.
Ejemplos y aplicaciones
La subdivisión barycentric de cualquier célula complejo C es un complejo bandera que tiene un vértice por célula de C . Una colección de vértices de la subdivisión baricéntrica forma un simplex si y solo si la colección correspondiente de celdas de C forma una bandera (una cadena en el orden de inclusión de las celdas). [3] En particular, la subdivisión baricéntrica de un complejo celular en una variedad 2 da lugar a una triangulación de Whitney de la variedad.
El complejo de orden de un conjunto parcialmente ordenado consta de las cadenas ( subconjuntos totalmente ordenados ) del orden parcial. Si cada par de algún subconjunto está ordenado en sí mismo, entonces todo el subconjunto es una cadena, por lo que el complejo de orden satisface la condición no Δ. Puede interpretarse como el complejo clique del gráfico de comparabilidad del orden parcial. [3]
El complejo de coincidencia de un gráfico consiste en los conjuntos de bordes, de los cuales no dos comparten un punto final; de nuevo, esta familia de conjuntos satisface la condición de no Δ. Puede ser visto como el complejo camarilla del grafo complemento del gráfico de línea de la gráfica dada. Cuando se hace referencia al complejo de coincidencia sin ningún gráfico en particular como contexto, significa el complejo de coincidencia de un gráfico completo . El complejo de emparejamiento de un gráfico bipartito completo K m , n se conoce como complejo de tablero de ajedrez . Es el gráfico de camarilla del gráfico de complemento de un gráfico de torre , [5] y cada uno de sus simples representa una ubicación de torres en un tablero de ajedrez de m × n de modo que dos torres no se ataquen entre sí. Cuando m = n ± 1, el complejo del tablero de ajedrez forma una pseudo-variedad .
El complejo Vietoris-Rips de un conjunto de puntos en un espacio métrico es un caso especial de un complejo clique, formado a partir del gráfico de disco unitario de los puntos; sin embargo, cada complejo de camarilla X (G) puede interpretarse como el complejo de Vietoris-Rips de la métrica de ruta más corta en el gráfico G subyacente .
Hodkinson y Otto (2003) describen una aplicación de hipergráficos conformes en la lógica de las estructuras relacionales. En ese contexto, el gráfico de Gaifman de una estructura relacional es el mismo que el gráfico subyacente del hipergráfico que representa la estructura, y una estructura está protegida si corresponde a un hipergráfico conforme.
Gromov demostró que un complejo cúbico (es decir, una familia de hipercubos que se cruzan cara a cara) forma un espacio CAT (0) si y solo si el complejo está simplemente conectado y el enlace de cada vértice forma un complejo de banderas. Un complejo cúbico que cumple con estas condiciones a veces se denomina cubicación o espacio con paredes . [1] [6]
Grupos de homología
Meshulam [7] demuestra el siguiente teorema sobre la homología del complejo clique. Enteros dados, suponga que una gráfica G satisface una propiedad llamada, Lo que significa que:
- Cada conjunto de los vértices en G tienen un vecino común;
- Existe un conjunto A de vértices, que contiene un vecino común a cada conjunto devértices, y además, el grafo inducido G [ A ] no contiene, como subgrafo inducido, una copia del esqueleto 1 de la esfera octaédrica t- dimensional .
Entonces la j -ésima homología reducida del complejo clique X ( G ) es trivial para cualquier j entre 0 y.
Ver también
- Gráfico simplex , una especie de gráfico que tiene un nodo para cada camarilla del gráfico subyacente
- Partition matroid , una especie de matroid cuyas intersecciones matroides pueden formar complejos de camarillas.
Notas
- ↑ a b Bandelt y Chepoi (2008) .
- ^ Hartsfeld y Ringel (1991) ; Larrión, Neumann-Lara y Pizaña (2002) ; Malnič y Mohar (1992) .
- ↑ a b c Davis (2002) .
- ^ Berge (1989) ; Hodkinson y Otto (2003) .
- ^ Dong y Wachs (2002) .
- ^ Chatterji y Niblo (2005) .
- ↑ Meshulam, Roy (1 de enero de 2001). "El complejo de la camarilla y la coincidencia de hipergráficos". Combinatorica . 21 (1): 89–94. doi : 10.1007 / s004930170006 . ISSN 1439-6912 . S2CID 207006642 .
Referencias
- Bandelt, H.-J .; Chepoi, V. (2008), "Teoría y geometría de grafos métricos: una encuesta", en Goodman, JE ; Pach, J .; Pollack, R. (eds.), Encuestas sobre geometría discreta y computacional: veinte años después (PDF) , Matemáticas contemporáneas, 453 , Providence, RI: AMS, págs. 49–86.
- Berge, C. (1989), Hipergrafos: Combinatoria de conjuntos finitos , Holanda Septentrional, ISBN 0-444-87489-5.
- Chatterji, I .; Niblo, G. (2005), "De los espacios en las paredes a los complejos de cubos CAT (0)", International Journal of Algebra and Computation , 15 (5–6): 875–885, arXiv : math.GT/0309036 , doi : 10.1142 / S0218196705002669 , S2CID 2786607.
- Davis, MW (2002), "Grupos de reflexión y curvatura no positiva", en Daverman, RJ; Sher, RB (eds.), Manual de topología geométrica , Elsevier, págs. 373–422.
- Dong, X .; Wachs, ML (2002), "Combinatorial Laplacian of the matching complex" , Electronic Journal of Combinatorics , 9 : R17, doi : 10.37236 / 1634.
- Hartsfeld, N .; Ringel, Gerhard (1991), "Triangulaciones limpias", Combinatorica , 11 (2): 145-155, doi : 10.1007 / BF01206358 , S2CID 28144260.
- Hodkinson, I .; Otto, M. (2003), "Cubiertas hipergráficas conformes finitas y camarillas de Gaifman en estructuras finitas", The Bulletin of Symbolic Logic , 9 (3): 387–405, CiteSeerX 10.1.1.107.5000 , doi : 10.2178 / bsl / 1058448678.
- Larrión, F .; Neumann-Lara, V .; Pizaña, MA (2002), "Triangulaciones de Whitney, circunferencia local y gráficas de clicas iteradas" , Matemáticas discretas , 258 (1-3): 123-135, doi : 10.1016 / S0012-365X (02) 00266-2.
- Malnič, A .; Mohar, B. (1992), "Generación de triangulaciones localmente cíclicas de superficies", Journal of Combinatorial Theory, Serie B , 56 (2): 147-164, doi : 10.1016 / 0095-8956 (92) 90015-P.