On the homology of independence complexes


Berghoff, M

Last Updated: 



The independence complex $\mathrm{Ind}(G)$ of a graph $G$ is the simplicial
complex formed by its independent sets. This article introduces a deformation
of the simplicial boundary map of $\mathrm{Ind}(G)$ that gives rise to a double
complex with trivial homology. Filtering this double complex in the right
direction induces a spectral sequence that converges to zero and contains on
its first page the homology of the independence complexes of $G$ and various
subgraphs of $G$, obtained by removing independent sets and their neighborhoods
from $G$. It is shown that this spectral sequence may 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 the
independence complexes of some subgraphs of $G$. This relation is shown to hold
for all paths and cyclic graphs.

Symplectic id: 


Download URL: 

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article