Skip to main content
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

On the homology of independence complexes

  • Author(s): Berghoff, Marko
  • et al.

Published Web Location Commons 'BY' version 4.0 license

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

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View