Independence complex

The independence complex of a graph is a mathematical object describing the independent sets of the graph. Formally, the independence complex of an undirected graph G, denoted by I(G), is an abstract simplicial complex (that is, a family of finite sets closed under the operation of taking subsets), formed by the sets of vertices in the independent sets of G. Any subset of an independent set is itself an independent set, so I(G) indeed meets the requirement of an abstract simplicial complex that every subset of a set in the family should also be in the family.

Every independent set in a graph is a clique in its complement graph, and vice-versa. Therefore, the independence complex of a graph equals the clique complex of its complement graph, and vice-versa.

Homology groups

Several authors studied the relations between the properties of a graph G = (V, E), and the homology groups of its independence complex I(G). In particular, several properties related to the dominating sets in G guarantee that some reduced homology groups of I(G) are trivial.

1. The total domination number of G, denoted $\gamma _{0}(G)$, is the minimum cardinality of a set total dominating set of G - a set S such that every vertex of V is adjacent to a vertex of S. If $\gamma _{0}(G)>k$ then ${\tilde {H}}_{k-1}(I(G))=0$.

2. The total domination number of a subset A of V in G, denoted $\gamma _{0}(G,A)$, is the minimum cardinality of a set S such that every vertex of A is adjacent to a vertex of S. If there exists an independent set A in G such that $\gamma _{0}(G,A)>k$ then ${\tilde {H}}_{k-1}(I(G))=0$.

3. The domination number of G, denoted $\gamma (G)$, is the minimum cardinality of a dominating set of G - a set S such that every vertex of V \ S is adjacent to a vertex of S. Note that $\gamma _{0}(G)\geq \gamma (G)$. If G is a chordal graph and $\gamma (G)>k$ then ${\tilde {H}}_{k-1}(I(G))=0$.

4. The induced matching number of G, denoted $\mu (G)$, is the largest cardinality of an induced matching in G - a matching that includes every edge connecting any two vertices in the subset. If there exists a subset A of V such that $\gamma _{0}(G,A)>k+\min[k,\mu (G[A])]$ then ${\tilde {H}}_{k-1}(I(G))=0$. This is a generalization of both properties 1 and 2 above.

5. The non-dominating independence complex of G, denoted I'(G), is the abstract simplicial complex of the independent sets that are not dominating sets of G. Obviously I'(G) is contained in I(G); denote the inclusion map by $i:I'(G)\to I(G)$. If G is a chordal graph then the induced map $i_{*}:{\tilde {H}}_{k}(I'(G))\to {\tilde {H}}_{k}(I(G))$ is zero for all $k\geq -1$. This is a generalization of property 3 above.

6. The fractional star-domination number of G, denoted $\gamma _{s}^{*}(G)$, is the minimum size of a fractional star-dominating set in G. If $\gamma _{s}^{*}(G)>k$ then ${\tilde {H}}_{k-1}(I(G))=0$.

Meshulam's game

Meshulam's game is a game used to explain a theorem of Roy Meshulam related to the homological connectivity of the independence complex of a graph. The formulation of this theorem as a game is due to Aharoni, Berger and Ziv.

The game-board is a graph G. It is a zero-sum game for two players, CON and NON. CON wants to show that I(G), the independence complex of G, has a high connectivity; NON wants to prove the opposite.

At his turn, CON chooses an edge e from the remaining graph. NON then chooses one of two options:

• Deletion – remove the edge e from the graph.
• Explosion – remove both endpoints of e, together with all their neighbors and the edges incident to them.

The score of CON is defined as follows:

• If at some point the remaining graph has an isolated vertex, the score is infinity;
• Otherwise, at some point the remaining graph contains no vertex; in that case the score is the number of explosions.

For every given graph G, the game value on G (i.e., the score of CON when both sides play optimally) is denoted by Ψ(G).

Meshulam proved that, for every graph G, the homological connectivity of I(G) is at least Ψ(G).

Related concepts

The matching complex of a graph G, denoted M(G), is an abstract simplicial complex of the matchings in G. It is the independence complex of the line graph of G.

The (m,n)-chessboard complex is the matching complex on the complete bipartite graph K_m,_n. It is the abstract simplicial complex of all sets of positions on an m-by-n chessboard, on which it is possible to put rooks without each of them threatening the other.

See also

• Rainbow-independent set