The equivariant topology of stable Kneser graphs

Abstract

The stable Kneser graph $S{G}_{n,k}$, $n\ge 1$, $k\ge 0$, introduced by Schrijver \cite{schrijver}, is a vertex critical graph with chromatic number $k+2$, its vertices are certain subsets of a set of cardinality $m=2n+k$. Björner and de Longueville \cite{anders-mark} have shown that its box complex is homotopy equivalent to a sphere, $\Hom(K_2,SG_{n,k})\homot\Sphere^k$. The dihedral group $D_{2m}$ acts canonically on $S{G}_{n,k}$, the group $C_2$ with 2 elements acts on $K_2$. We almost determine the $(C_2\times D_{2m})$-homotopy type of $\Hom(K_2,SG_{n,k})$ and use this to prove the following results. The graphs $S{G}_{2s,4}$ are homotopy test graphs, i.e. for every graph $H$ and $r\ge 0$ such that $\Hom(SG_{2s,4},H)$ is $(r-1)$-connected, the chromatic number $\chi (H)$ is at least $r+6$. If $k\notin \{0,1,2,4,8\}$ and $n\ge N(k)$ then $S{G}_{n,k}$ is not a homotopy test graph, i.e.\ there are a graph $G$ and an $r\ge 1$ such that $\Hom(SG_{n,k}, G)$ is $(r-1)$-connected and $\chi (G)<r+k+2$.

34 pp.

References in corpus (1)

• The universality of Hom complexes

Cited by in corpus (2)

• Paths of homomorphisms from stable Kneser graphs
• Deformation Retracts of Neighborhood Complexes of Stable Kneser Graphs