complejo de camarilla

Los complejos de cliques , los complejos de independencia, los complejos de banderas , 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 cada uno de los cliques (subgrafos completos) de un grafo no dirigido .

El complejo de cliques 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 a su vez un clique, por lo que esta familia de conjuntos cumple el requisito de un complejo simplicial abstracto de que todo subconjunto de un conjunto en la familia también debe estar en la familia.

El complejo de cliques también puede verse 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 1-esqueleto de X ( G ) (también conocido como el grafo subyacente del complejo) es un grafo no dirigido con un vértice por cada conjunto de 1 elemento en la familia y una arista por cada conjunto de 2 elementos en la familia; es isomorfo a G . ^{[ 1 ]}

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 de clique de G es equivalente al complejo de independencia del grafo complemento 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 cliques es un complejo de banderas: si cada par de vértices en S es un clique de tamaño 2, entonces hay una arista entre ellos, por lo que S es un clique.

Todo complejo de banderas es un complejo de cliques: dado un complejo de banderas, definimos un grafo G sobre el conjunto de todos los vértices, donde dos vértices u,v son adyacentes en G si y solo si {u,v} pertenece al complejo (este grafo se denomina el 1-esqueleto del complejo). Por definición de un complejo de banderas, todo conjunto de vértices conectados por pares pertenece al complejo. Por lo tanto, el complejo de banderas es igual al complejo de cliques sobre 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 datos distintos a un grafo, en lugar de indirectamente como el complejo de camarillas de un grafo derivado de esos datos. ^{[ 2 ]}

Mikhail Gromov definió la condición no- Δ como la condición de ser un complejo de banderas.

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 sobre 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 celular 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 único ciclo. ^{[ 3 ]}

El grafo primal 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 clique maximal de su grafo primal es una hiperarista, o equivalentemente, si cada clique de su grafo primal está contenido en alguna hiperarista. ^{[ 4 ]} Si se requiere que el hipergrafo sea 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 banderas. 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 banderas que tiene un vértice por celda 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 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 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 algún subconjunto está ordenado a su vez, entonces todo el subconjunto es una cadena, por lo que el complejo de orden satisface la condición de no-Δ. Puede interpretarse como el complejo de clique del grafo de comparabilidad del orden parcial. ^{[ 2 ]}

El complejo de emparejamiento de un grafo consiste en los conjuntos de aristas que no comparten un extremo; nuevamente, esta familia de conjuntos satisface la condición no-Δ. Puede verse como el complejo de clique del grafo complemento del grafo de línea del grafo dado. Cuando se hace referencia al complejo de emparejamiento sin ningún grafo particular como contexto, significa el complejo de emparejamiento de un grafo completo . El complejo de emparejamiento de un grafo bipartito completo K _{m , n} se conoce como un complejo de tablero de ajedrez . Es el grafo de clique del grafo complemento de un grafo de torres , ^{[ 5 ]} y cada uno de sus símplices representa una colocación de torres en un tablero de ajedrez m × n tal que no dos de las torres se atacan 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 clique, formado a partir del grafo de disco unitario de los puntos; sin embargo, todo complejo de clique X(G) puede interpretarse como el complejo de Vietoris-Rips de la métrica de camino más corto en el grafo subyacente G.

Hodkinson y Otto (2003) describen una aplicación de los 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 se considera 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 enlace de cada vértice forma un complejo de banderas. Un complejo cúbico que cumple estas condiciones se denomina a veces cubo o espacio con paredes . ^{[ 1 ] [ 6 ]}

Meshulam ^{[ 7 ]} demuestra el siguiente teorema sobre la homología del complejo de cliques. Dados los enteros${\displaystyle l\geq 1,t\geq 0}$Supongamos que un grafo G satisface una propiedad llamada${\displaystyle P(l,t)}$, lo que significa que:

• Cada conjunto de${\displaystyle l}$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 de${\displaystyle l}$vértices, y además, el grafo inducido G [ A ] no contiene, como subgrafo inducido, una copia del 1-esqueleto de la esfera octaédrica t- dimensional .

Entonces, la j -ésima homología reducida del complejo de clique X( G ) es trivial para cualquier j entre 0 y${\displaystyle \max(lt,\lfloor {l}/{2}\rfloor )-1}$.

• Grafo simplex , un tipo de grafo que tiene un nodo por cada camarilla del grafo subyacente.
• Matroide de partición , un tipo de matroide cuyas intersecciones pueden formar complejos de cliques.

• Bandelt, H.-J.; Chepoi, V. (2008), "Teoría de grafos métricos y geometría: una revisión", en Goodman, JE ; Pach, J .; Pollack, R. (eds.), Revisiones sobre geometría discreta y computacional: veinte años después (PDF) , Contemporary Mathematics, vol.  453, Providence, RI: AMS, pp . 49–86 .
• Berge, C. (1989), Hipergrafos: Combinatoria de conjuntos finitos , North-Holland, ISBN 0-444-87489-5.
• Chatterji, I.; Niblo, G. (2005), "From wall spaces to CAT(0) cube complexes", International Journal of Algebra and Computation , 15 ( 5–6 ): 875–885 , arXiv : math.GT/0309036 , doi : 10.1142/S0218196705002669 , S2CID 2786607 .
• Davis, MW ( 2002), "Curvatura no positiva y grupos de reflexión", en Daverman, RJ ; Sher, RB (eds.), Manual de topología geométrica , Elsevier, pp. 373–422 .
• Dong, X.; Wachs, ML (2002), "Laplaciano combinatorio del complejo de emparejamiento" , 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), "Recubrimientos de hipergrafos conformes finitos 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 grafos de cliques iterados" , 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.