ARS Avanzado: Complejo clique

Complejo clique
Wikipedia



El complejo clique de un grafo. Los grupos de tamaño uno se muestran como pequeños discos rojos; grupos de tamaño 2 se muestran como segmentos de líneas negras; grupos de tamaño 3 se muestran como triángulos de color azul claro; y grupos de tamaño 4 o tetraedros se muestran de color azul oscuro.


Los complejos cliques, complejos de bandera, e hipergrafos conformales son objetos matemáticos que están relacionados estrechamente con la teoría de grafos y la topología geométrica que cada uno describen 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 toma de subconjuntos), formada 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 en el que cada subconjunto de un conjunto en la familia también debe estar en la familia. El complejo clique también puede ser visto como un espacio topológico en el que cada camarilla 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 un enlace para cada conjunto de 2 elementos en la familia; es isomorfo a G. [1]

Los complejos clique son también conocidos como complejos de Whitney. Una triangulación Whitney o triangulación limpio de un colector (manifold) de dos dimensiones es una incrustación de un grafo de G en el colector 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 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 al colector subyacente. Un grafo G tiene un complejo clique de 2 colectores (manifold), y puede ser incrustado como una triangulación Whitney, si y sólo 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. [2]

Complejo de independencia

El complejo independencia I (G) de un grafo G se forma de la misma manera como el complejo camarilla de los conjuntos independientes de G. Es el complejo camarilla del grafo complemento de G.

Complejo de bandera

En un complejo simplicial abstracto, un conjunto S de vértices que no es en sí parte del complejo, pero de tal manera que cada par de vértices en S pertenece a algún simplex en el complejo, que se llama un simplex vacío. Mikhail Gromov define la condición de no-Δ ser la condición de que un complejo no tienen simplices vacías. Un complejo bandera es un complejo simplicial abstracto que no tiene simplices vacías; es decir, que es la condición no-Δ un complejo de Gromov satisfacer. Cualquier complejo bandera es el complejo de su camarilla 1-esqueleto. Por lo tanto, los complejos y los complejos bandera camarilla son esencialmente la misma cosa. Sin embargo, en muchos casos puede ser conveniente definir un complejo bandera directamente de algunos datos distintos de un grafo, en lugar de indirectamente como el complejo clique de un grafo derivado de los datos. [3]

Conforme de hipergrafo

El grafo primario G (H) de un hipergrafo es el grafo en el mismo conjunto de vértices que tiene como sus enlaces los pares de vértices que aparecen juntos en la misma hiperenlace. Un hipergrafo se dice que es conforme si cada camarilla máxima de su grafo es un hipernelace primitivo, o equivalentemente, si cada camarilla de su grafo primario está contenida en alguna hiperenlace. [4] Si se requiere el hipergrafo sea descendente cerrado (por lo que contiene todos los hiperenlaces que se contienen en algunos hiperenlaces) entonces el hipergrafo es conforme con precisión cuando se trata de un complejo de bandera. Esto se relaciona el lenguaje de hipergrafos al lenguaje del complejo simplicial.

Ejemplos y aplicaciones

La subdivisión baricéntrica de cualquier complejo C de células es un complejo de bandera que tiene un vértice por célula de C. Una colección de vértices de la subdivisión baricéntrica formar un simplex si y sólo si la colección correspondiente de células de C forman una bandera (una cadena en el inclusión de pedido de las células). [3] En particular, la subdivisión barycentric de un complejo celular en un 2-colector da lugar a una triangulación Whitney del colector.

El complejo orden de un conjunto parcialmente ordenado se compone de las cadenas (subconjuntos totalmente ordenado) del orden parcial. Si cada par de algún subconjunto es en sí mismo ordenó, entonces todo el subconjunto es una cadena, por lo que los complejos satisface la condición de la orden de no-Δ. Se puede interpretar como el complejo camarilla del grafo de la comparabilidad de la orden parcial. [3]

El complejo de empardamiento (matching complex) de un grafo consiste en los conjuntos de enlaces ninguno de cuyos pares 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 grafo de líneas del grafo dado. Cuando el complejo juego se denomina sin ninguna representación grafo concreta como contexto, significa el complejo juego de un grafo completo. El complejo juego de un grafo bipartito completo K_m,n es conocida como un complejo de tablero de ajedrez. Es el clique de del grafo complemento del grafo de una torre, [5] y cada uno de sus simplices representa una colocación de torres en un tablero de m × n de ajedrez de tal manera que no hay dos de las torres atacan entre sí. Cuando m = n ± 1, las formas complejas de tablero de ajedrez una pseudo-colector.

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 grafo de disco unidad de los puntos; Sin embargo, cada complejo clique X(G) puede ser interpretada como el complejo Vietoris-Rips de la métrica camino más corto en el grafo subyacente G.

Hodkinson y Otto (2003) describen una aplicación de hipergrafos conformales 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é vigilado si corresponde a un hipergrafo conformal.

Gromov mostró que un complejo cúbico (es decir, una familia de hipercubos intersección cara a cara) forma un CAT (0) espacio si y sólo si el complejo está simplemente conectado y el enlace de cada vértice forma un complejo bandera. Una reunión compleja cúbica estas condiciones a veces se llama una cubicación o un espacio con paredes. [1] [6]

Referencias

1. Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J. E.; Pach, J.; Pollack, R., Surveys on Discrete and Computational Geometry: Twenty Years Later (PDF), Contemporary Mathematics, 453, Providence, RI: AMS, pp. 49–86.
2. Berge, C. (1989), Hypergraphs: Combinatorics of Finite Sets, North-Holland, ISBN 0-444-87489-5.
3. 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.
4. Davis, M. W. (2002), "Nonpositive curvature and reflection groups", in Daverman, R. J.; Sher, R. B., Handbook of Geometric Topology, Elsevier, pp. 373–422.
5. Dong, X.; Wachs, M. L. (2002), "Combinatorial Laplacian of the matching complex", Electronic Journal of Combinatorics, 9: R17.
6. Hartsfeld, N.; Ringel, Gerhard (1991), "Clean triangulations", Combinatorica, 11 (2): 145–155, doi:10.1007/BF01206358.
7. Hodkinson, I.; Otto, M. (2003), "Finite conformal hypergraph covers and Gaifman cliques in finite structures", The Bulletin of Symbolic Logic, 9 (3): 387–405, doi:10.2178/bsl/1058448678.
8. Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics, 258: 123–135, doi:10.1016/S0012-365X(02)00266-2.
9. Malnič, A.; Mohar, B. (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B, 56 (2): 147–164, doi:10.1016/0095-8956(92)90015-P.