Los complejos de camarilla , 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 y cada uno de ellos describe las camarillas (subgrafos completos) de un gráfico no dirigido .
El complejo de camarilla 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 las camarillas de G. Cualquier subconjunto de una camarilla es en sí misma 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 de la familia también debe estar en la familia.
El complejo de camarilla también puede verse como un espacio topológico en el que cada camarilla de k vértices está representada por un simplex de dimensión k – 1 . El 1-esqueleto de X ( G ) (también conocido como 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 una arista para cada conjunto de 2 elementos de la familia; es isomorfo a G . [1]
Todo complejo de camarilla es un complejo simplicial abstracto, pero lo contrario no es cierto. Por ejemplo, considere el complejo simplicial abstracto sobre {1,2,3,4} con conjuntos máximos {1,2,3}, {2,3,4}, {4,1}. Si fuera la X ( G ) de algún gráfico G , entonces G tení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 la camarilla {1,2,3,4}.
El complejo de independencia I ( G ) de un gráfico no dirigido G es un complejo simplicial abstracto formado por los conjuntos de vértices en los conjuntos independientes de G . El complejo de camarilla de G es equivalente al complejo de independencia del gráfico de complemento de G.
Un complejo de banderas es un complejo simplicial abstracto con una propiedad adicional llamada "determinado por 2": 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.
Cada 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.
Cada complejo de bandera es un complejo de camarilla: dado un complejo de bandera, defina un gráfico G en el conjunto de todos los vértices, donde dos vértices u,v son adyacentes en G si {u,v} está en el complejo (este gráfico se llama 1-esqueleto del complejo). Por definición de complejo de banderas, cada conjunto de vértices que están conectados por pares está en el complejo. Por lo tanto, el complejo de bandera es igual al complejo de camarilla en G.
Por tanto, los complejos de bandera y los complejos de camarilla son esencialmente la misma cosa. 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 camarilla 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 camarilla 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 gráfico G en la variedad de tal manera que cada cara es un triángulo y cada triángulo es una cara. Si un gráfico G tiene una triangulación de Whitney, debe formar un complejo celular que sea isomorfo al complejo de Whitney de G. En este caso, el complejo (visto como un espacio topológico) es homeomorfo con respecto a la variedad subyacente. Un gráfico G tiene un complejo de camarilla de 2 variedades y puede incluirse como una triangulación de Whitney, si y sólo si G es localmente cíclico ; esto significa que, para cada vértice v del gráfico, el subgrafo inducido formado por los vecinos de v forma un solo ciclo. [3]
El gráfico primario G ( H ) de un hipergrafo es el gráfico en el mismo conjunto de vértices que tiene como aristas los pares de vértices que aparecen juntos en el mismo hiperarista . Se dice que un hipergrafo es conforme si cada camarilla máxima de su grafo primario es un hiperborde, o de manera equivalente, si cada camarilla de su grafo primario está contenida en algún hiperborde. [4] Si se requiere que el hipergrafo esté cerrado hacia abajo (por lo que contiene todos los hiperbordes que están contenidos en algún hiperborde), 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 de bandera que tiene un vértice por celda de C. Una colección de vértices de la subdivisión baricéntrica forma un simplex si y sólo si la correspondiente colección de celdas de C forma una bandera (una cadena en el orden de inclusión de las celdas). [2] En particular, la subdivisión baricéntrica de un complejo celular en una variedad de 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, entonces todo el subconjunto es una cadena, por lo que el complejo de orden satisface la condición no-Δ. Puede interpretarse como el complejo de camarilla del gráfico de comparabilidad del orden parcial. [2]
El complejo coincidente de un gráfico consta de conjuntos de aristas de las cuales no hay dos que compartan un punto final; nuevamente, esta familia de conjuntos satisface la condición no-Δ. Puede verse como el complejo de camarilla del gráfico complementario del gráfico lineal del gráfico dado. Cuando se hace referencia al complejo coincidente sin ningún gráfico en particular como contexto, se refiere al complejo coincidente de un gráfico completo . El complejo coincidente de un gráfico bipartito completo Km , n se conoce como complejo de tablero de ajedrez . Es el gráfico de camarilla del gráfico de complemento del gráfico de una torre , [5] y cada uno de sus símplices representa una ubicación de torres en un tablero de ajedrez de m × n de modo que dos de las torres no se ataquen entre sí. Cuando m = n ± 1, el complejo del 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 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 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 sólo si el complejo es simplemente conexo y el vínculo de cada vértice forma un complejo de bandera. Un complejo cúbico que cumple estas condiciones a veces se denomina cubo o espacio con paredes . [ dieciséis]
Meshulam [7] demuestra el siguiente teorema sobre la homología del complejo de camarilla. Dados números enteros , supongamos que un gráfico G satisface una propiedad llamada , 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 .
