Los complejos de camarillas , los complejos de independencia, los complejos de bandera , los complejos de Whitney y los hipergrafos conformes son objetos matemáticos estrechamente relacionados en la teoría de grafos y la topología geométrica que describen las camarillas (subgrafos completos) de un grafo no dirigido .
El complejo clique X ( G ) de un grafo no dirigido G es un complejo simplicial abstracto (es decir, una familia de conjuntos finitos cerrados bajo la operación de tomar subconjuntos), formado por los conjuntos de vértices en los cliques de G . Cualquier subconjunto de un clique es en sí mismo un clique, por lo que esta familia de conjuntos cumple 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 de camarillas también puede verse como un espacio topológico en el que cada camarilla de k vértices está representada por un símplex de dimensión k – 1. El 1-esqueleto de X ( G ) (también conocido como el grafo subyacente del complejo) es un grafo no dirigido con un vértice para cada conjunto de 1 elemento en la familia y una arista para cada conjunto de 2 elementos en la familia; es isomorfo a G . [1]
Todo complejo clique es un complejo simplicial abstracto, pero lo opuesto no es cierto. Por ejemplo, considere el complejo simplicial abstracto sobre {1,2,3,4} con conjuntos maximales {1,2,3}, {2,3,4}, {4,1}. Si fuera el X ( G ) de algún grafo G , entonces G tendría que tener las aristas {1,2}, {1,3}, {2,3}, {2,4} , {3,4}, {4,1}, por lo que X ( G ) también debería contener el clique {1,2,3,4}.
El complejo de independencia I ( G ) de un grafo no dirigido G es un complejo simplicial abstracto formado por los conjuntos de vértices en los conjuntos independientes de G . El complejo clique de G es equivalente al complejo de independencia del grafo complementario de G .
Un complejo de banderas es un complejo simplicial abstracto con una propiedad adicional llamada "2-determinado": para cada subconjunto S de vértices, si cada par de vértices en S está en el complejo, entonces S mismo también está en el complejo.
Todo complejo de camarilla es un complejo de bandera: si cada par de vértices en S es una camarilla de tamaño 2, entonces hay una arista entre ellos, por lo que S es una camarilla.
Todo complejo de banderas es un complejo de camarilla: dado un complejo de banderas, defina un grafo G en el conjunto de todos los vértices, donde dos vértices u,v son adyacentes en G si y solo si {u,v} está en el complejo (este grafo se denomina el 1-esqueleto del complejo). Por definición de un complejo de banderas, cada conjunto de vértices que están conectados por pares está en el complejo. Por lo tanto, el complejo de banderas es igual al complejo de camarilla en G.
Por lo tanto, los complejos de banderas y los complejos de camarillas son esencialmente lo mismo. 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 camarillas de un gráfico derivado de esos datos. [2]
Mikhail Gromov definió la condición no-Δ como la condición de ser un complejo de bandera.
Los complejos de clique también se conocen como complejos de Whitney , en honor a Hassler Whitney . Una triangulación de Whitney o triangulación limpia de una variedad bidimensional es una incrustación de un grafo G en la variedad de tal manera que cada cara es un triángulo y cada triángulo es una cara. Si un grafo G tiene una triangulación de Whitney, debe formar un complejo de celdas que sea isomorfo al complejo de Whitney de G. En este caso, el complejo (visto como un espacio topológico) es homeomorfo a la variedad subyacente. Un grafo G tiene un complejo de clique de 2 variedades y puede incrustarse 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 grafo, el subgrafo inducido formado por los vecinos de v forma un solo ciclo. [3]
El grafo primario G ( H ) de un hipergrafo es el grafo sobre el mismo conjunto de vértices que tiene como aristas los pares de vértices que aparecen juntos en la misma hiperarista . Se dice que un hipergrafo es conforme si cada camarilla maximal de su grafo primario es una hiperarista, o equivalentemente, si cada camarilla de su grafo primario está contenida en alguna hiperarista. [4] Si se requiere que el hipergrafo esté cerrado hacia abajo (de modo que contenga todas las hiperaristas que están contenidas en alguna hiperarista), entonces el hipergrafo es conforme precisamente cuando es un complejo de bandera. Esto relaciona el lenguaje de los hipergrafos con el lenguaje de los complejos simpliciales.
La subdivisión baricéntrica de cualquier complejo celular 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 símplex si y solo si la colección correspondiente de células de C forma una bandera (una cadena en el orden de inclusión de las células). [2] En particular, la subdivisión baricéntrica de un complejo celular en una 2-variedad da lugar a una triangulación de Whitney de la variedad.
El complejo de orden de un conjunto parcialmente ordenado consiste en las cadenas ( subconjuntos totalmente ordenados ) del orden parcial. Si cada par de un subconjunto está ordenado, entonces el subconjunto completo es una cadena, por lo que el complejo de orden satisface la condición de no-Δ. Puede interpretarse como el complejo de clique del gráfico de comparabilidad del orden parcial. [2]
El complejo coincidente de un grafo consiste en los conjuntos de aristas de las cuales no hay dos que compartan un punto final; nuevamente, esta familia de conjuntos satisface la condición de no-Δ. Puede verse como el complejo de camarilla del grafo complementario del grafo lineal del grafo dado. Cuando se hace referencia al complejo coincidente sin ningún grafo particular como contexto, se refiere al complejo coincidente de un grafo completo . El complejo coincidente de un grafo bipartito completo K m , n se conoce como complejo de tablero de ajedrez . Es el grafo de camarilla del grafo complementario del grafo de una torre , [5] y cada uno de sus símplices representa una colocación de torres en un tablero de ajedrez m × n tal que ninguna de las torres se ataque entre sí. Cuando m = n ± 1, el complejo de tablero de ajedrez forma una pseudovariedad .
El complejo de Vietoris-Rips de un conjunto de puntos en un espacio métrico es un caso especial de un complejo de camarilla, 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 del camino más corto en el gráfico subyacente G.
Hodkinson y Otto (2003) describen una aplicación de hipergrafos conformes en la lógica de las estructuras relacionales. En ese contexto, el grafo de Gaifman de una estructura relacional es el mismo que el grafo subyacente del hipergrafo que representa la estructura, y una estructura está protegida si corresponde a un hipergrafo conforme.
Gromov demostró que un complejo cúbico (es decir, una familia de hipercubos que se intersecan cara a cara) forma un espacio CAT(0) si y solo si el complejo es simplemente conexo y el vínculo de cada vértice forma un complejo bandera. Un complejo cúbico que cumple estas condiciones a veces se denomina cubo o espacio con paredes . [1] [6]
Meshulam [7] demuestra el siguiente teorema sobre la homología del complejo clique. Dados los números enteros , supongamos que un grafo G satisface una propiedad denominada , lo que significa que:
Entonces la j -ésima homología reducida del complejo de camarilla X( G ) es trivial para cualquier j entre 0 y .
