complejo de 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 a su vez un conjunto independiente, por lo que I( G ) es efectivamente cerrado bajo la operación de tomar subconjuntos.

Todo conjunto independiente en un grafo es una camarilla en su grafo complemento , y viceversa. Por lo tanto, el complejo de independencia de un grafo es igual al complejo de camarilla de su grafo complemento, y viceversa.

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 ) son triviales.

1. El número total de dominación de G, denotado${\displaystyle \gamma _{0}(G)}$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${\displaystyle \gamma _{0}(G)>k}$entonces${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$. ^{[ 2 ]}

2. El número total de dominación de un subconjunto A de V en G, denotado${\displaystyle \gamma _{0}(G,A)}$, 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${\displaystyle i\gamma (G)}$, es el máximo, sobre todos los conjuntos independientes A en G , de ${\displaystyle \gamma _{0}(G,A)}$. Si ${\displaystyle i\gamma (G)>k}$, entonces${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$. ^{[ 1 ] [ 3 ]}

3. El número de dominación de G , denotado${\displaystyle \gamma (G)}$, 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${\displaystyle \gamma _{0}(G)\geq \gamma (G)}$. Si G es un grafo cordal y${\displaystyle \gamma (G)>k}$entonces${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$. ^{[ 4 ]}

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

5. El complejo de independencia 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 aplicación de inclusión por${\displaystyle i:I'(G)\to I(G)}$. Si G es un grafo cordal , entonces el mapa inducido${\displaystyle i_{*}:{\tilde {H}}_{k}(I'(G))\to {\tilde {H}}_{k}(I(G))}$es cero para todos${\displaystyle k\geq -1}$. ^{[ 1 ] : Teorema 1.4} Esta es una generalización de la propiedad 3 anterior.

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

El juego de Meshulam es un juego que se juega en un grafo G , que se puede utilizar para calcular una cota inferior de la conectividad homológica del complejo de independenciade 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 de líneas de G. ^{[ 6 ] [ 7 ]}

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

El complejo de clique de G es el complejo de independencia del grafo complemento de G.

• Conjunto independiente de Rainbow