Complejo de la Independencia

El complejo de independencia de un grafo es un objeto matemático que describe los conjuntos independientes del grafo. Formalmente, el complejo de independencia de un grafo no dirigido G , denotado por I( 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 conjuntos independientes de G . Cualquier subconjunto de un conjunto independiente es en sí mismo un conjunto independiente, por lo que I( G ) es de hecho cerrado bajo la operación de tomar subconjuntos.

Todo conjunto independiente de un grafo es un conjunto clique de su grafo complementario , y viceversa. Por lo tanto, el complejo independiente de un grafo es igual al complejo clique de su grafo complementario, y viceversa.

Grupos de homología

Varios autores estudiaron las relaciones entre las propiedades de un grafo G = ( V , E ), y los grupos de homología de su complejo de independencia I( G ). ^[1] En particular, varias propiedades relacionadas con los conjuntos dominantes en G garantizan que algunos grupos de homología reducidos de I( G ) sean triviales.

1. El número de dominación total de G, denotado , es la cardinalidad mínima de un conjunto dominante total de G - un conjunto S tal que cada vértice de V es adyacente a un vértice de S . Si entonces . ^[2] ${\displaystyle \gamma _{0}(G)}$ ${\displaystyle \gamma _{0}(G)>k}$ ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

2. El número de dominación total de un subconjunto A de V en G, denotado , es la cardinalidad mínima de un conjunto S tal que cada vértice de A es adyacente a un vértice de S . El número de dominación de independencia de G, denotado , es el máximo, sobre todos los conjuntos independientes A en G , de . Si , entonces . ^{[1] [3]} ${\displaystyle \gamma _{0}(G,A)}$ ${\displaystyle i\gamma (G)}$ ${\displaystyle \gamma _{0}(G,A)}$ ${\displaystyle i\gamma (G)>k}$ ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

3. El número de dominación de G , denotado , es la cardinalidad mínima de un conjunto dominante de G - un conjunto S tal que cada vértice de V \ S es adyacente a un vértice de S . Nótese que . Si G es un grafo cordal y entonces . ^[4] ${\displaystyle \gamma (G)}$ ${\displaystyle \gamma _{0}(G)\geq \gamma (G)}$ ${\displaystyle \gamma (G)>k}$ ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

4. El número de coincidencia inducida de G , denotado , es la cardinalidad más grande de una coincidencia inducida en G , una coincidencia que incluye cada arista que conecta dos vértices cualesquiera en el subconjunto. Si existe un subconjunto A de V tal que entonces . ^[5] Esta es una generalización de las propiedades 1 y 2 anteriores. ${\displaystyle \mu (G)}$ ${\displaystyle \gamma _{0}(G,A)>k+\min[k,\mu (G[A])]}$ ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

5. El complejo independiente no dominante de G, denotado I'( G ), es el complejo simplicial abstracto de los conjuntos independientes que no son conjuntos dominantes de G . Obviamente I'( G ) está contenido en I( G ); denotemos la función de inclusión por . Si G es un grafo cordal entonces la función inducida es cero para todo . ^{[1] : Teoría 1.4} Esta es una generalización de la propiedad 3 anterior. ${\displaystyle i:I'(G)\to I(G)}$ ${\displaystyle i_{*}:{\tilde {H}}_{k}(I'(G))\to {\tilde {H}}_{k}(I(G))}$ ${\displaystyle k\geq -1}$

6. El número de dominación estelar fraccionaria de G, denotado , es el tamaño mínimo de un conjunto de dominación estelar fraccionaria en G . Si entonces . ^{[1] : Teoría 1.5} ${\displaystyle \gamma _{s}^{*}(G)}$ ${\displaystyle \gamma _{s}^{*}(G)>k}$ ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

Conceptos relacionados

El juego de Meshulam es un juego que se juega en un gráfico G , que puede usarse para calcular un límite inferior en la conectividad homológica del complejo de independencia de G .

El complejo de emparejamiento de un grafo G , denotado M( G ), es un complejo simplicial abstracto de los emparejamientos en G . Es el complejo de independencia del grafo lineal de G . ^{[6] [7]}

El complejo de tablero de ajedrez ( m , n ) es el complejo correspondiente en el grafo bipartito completo K _m , _n . Es el complejo simplicial abstracto de todos los conjuntos de posiciones en un tablero de ajedrez de m por n , en el que es posible colocar torres sin que cada una de ellas amenace a la otra. ^{[8] [9]}

El complejo de camarilla de G es el complejo de independencia del gráfico de complemento de G.

Véase también

• Conjunto independiente del arco iris

Referencias

1. Meshulam, Roy (1 de mayo de 2003). "Números de dominación y homología". Journal of Combinatorial Theory, Serie A . 102 (2): 321–330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN  0097-3165.
2. Chudnovsky, Maria (2000). Sistemas de representantes disjuntos (tesis de maestría) . Haifa, Israel: Technion, departamento de matemáticas.
3. Aharoni, Ron; Haxell, Penny (2000). "Teorema de Hall para hipergrafos". Revista de teoría de grafos . 35 (2): 83–88. doi :10.1002/1097-0118(200010)35:2<83::aid-jgt2>3.0.co;2-v. ISSN  0364-9024.
4. Aharoni, Ron; Berger, Eli; Ziv, Ran (1 de julio de 2002). "Una versión en árbol del teorema de Kőnig". Combinatoria . 22 (3): 335–343. doi :10.1007/s004930200016. ISSN  0209-9683. S2CID  38277360.
5. Meshulam, Roy (1 de enero de 2001). "El complejo de camarillas y la correspondencia de hipergrafos". Combinatorica . 21 (1): 89–94. doi :10.1007/s004930170006. ISSN  1439-6912. S2CID  207006642.
6. Björner, A.; Lovász, L.; Vrećica, ST; Živaljević, RT (1994). "Complejos de tablero de ajedrez y complejos de emparejamiento". Revista de la Sociedad Matemática de Londres . 49 (1): 25–39. doi :10.1112/jlms/49.1.25. ISSN  1469-7750.
7. Reiner, Victor; Roberts, Joel (1 de marzo de 2000). "Resoluciones mínimas y homología de los complejos de emparejamiento y de tablero de ajedrez". Journal of Algebraic Combinatorics . 11 (2): 135–154. doi : 10.1023/A:1008728115910 . ISSN  1572-9192.
8. Friedman, Joel; Hanlon, Phil (1998-09-01). "Sobre los números de Betti de los complejos de tablero de ajedrez". Journal of Algebraic Combinatorics . 8 (2): 193–203. doi : 10.1023/A:1008693929682 . hdl : 2027.42/46302 . ISSN  1572-9192.
9. Ziegler, Günter M. (1994-02-01). "Capacidad de descascarillado de complejos de tablero de ajedrez". Revista israelí de matemáticas . 87 (1): 97–110. doi :10.1007/BF02772986. ISSN  1565-8511. S2CID  59040033.