2010/03/29 by Carsten Schultz, Schultz, Carsten · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics #Homotopy and Cohomology in Algebraic Topology #Topological and Geometric Data Analysis
paper · doi:10.48550/arxiv.1003.5688
openalex publication_date 2010/03/29 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
The stable Kneser graph SGn,k, n≥1, k≥0, introduced by Schrijver \citeschrijver, 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 \citeanders-mark have shown that its box complex is homotopy equivalent to a sphere, \Hom(K2,SGn,k)\homot\Spherek. The dihedral group D2m acts canonically on SGn,k, the group C2 with 2 elements acts on K2. We almost determine the (C2× D2m)-homotopy type of \Hom(K2,SGn,k) and use this to prove the following results. The graphs SG2s,4 are homotopy test graphs, i.e. for every graph H and r≥0 such that \Hom(SG2s,4,H) is (r-1)-connected, the chromatic number χ(H) is at least r+6. If k∉\set0,1,2,4,8 and n≥ N(k) then SGn,k is not a homotopy test graph, i.e. there are a graph G and an r≥1 such that \Hom(SGn,k, G) is (r-1)-connected and χ(G)