Combinatorial Theory

The independence complex \(\mathrm{Ind}(G)\) of a graph \(G\) is the simplicial complex formed by its independent sets of vertices. We introduce a deformation of the simplicial chain complex of \(\mathrm{Ind}(G)\) that gives rise to a spectral sequence which contains on its first page the homology groups of the independence complexes of \(G\) and various subgraphs of \(G\), obtained by removing independent sets together with their neighborhoods. We show how this can be used to study the homology of \(\mathrm{Ind}(G)\). Furthermore, a careful investigation of the sequence's first page exhibits a relation between the cardinality of maximal independent sets in \(G\) and the vanishing of certain homology groups of independence complexes of subgraphs of \(G\). We show that it holds for all paths and cycles.

Mathematics Subject Classifications: 05C69, 55U10