Independence complexes of stable Kneser graphs (Q540129): Difference between revisions

Summary: For integers \(n \geq 1\), \(k \geq 0\), the stable Kneser graph \(SG_{n,k}\) (also called the Schrijver graph) has as vertex set the stable \(n\)-subsets of \([2n + k]\) and as edges disjoint pairs of \(n\)-subsets, where a stable \(n\)-subset is one that does not contain any 2-subset of the form \({i, i + 1}\) or \({1, 2n + k}\). The stable Kneser graphs have been an interesting object of study since the late 1970's when A. Schrijver determined that they are a vertex critical class of graphs with chromatic number \(k + 2\). This article contains a study of the independence complexes of \(SG_{n,k}\) for small values of \(n\) and \(k\). Our contributions are two-fold: first, we prove that the homotopy type of the independence complex of \(SG_{2,k}\) is a wedge of spheres of dimension two. Second, we determine the homotopy types of the independence complexes of certain graphs related to \(SG_{n,2}\).