Skip to Main content Skip to Navigation
Conference papers

The equivariant topology of stable Kneser graphs

Abstract : Schrijver introduced the stable Kneser graph $SG_{n,k}, n \geq 1, k \geq 0$. This graph 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 have shown that its box complex is homotopy equivalent to a sphere, $\mathrm{Hom}(K_2,SG_{n,k}) \simeq \mathbb{S}^k$. The dihedral group $D_{2m}$ acts canonically on $SG_{n,k}$. We study the $D_{2m}$ action on $\mathrm{Hom}(K_2,SG_{n,k})$ and define a corresponding orthogonal action on $\mathbb{R}^{k+1} \supset \mathbb{S}^k$. We establish a close equivariant relationship between the graphs $SG_{n,k}$ and Borsuk graphs of the $k$-sphere and use this together with calculations in the $\mathbb{Z}_2$-cohomology ring of $D_{2m}$ to tell which stable Kneser graphs are test graphs in the sense of Babson and Kozlov. The graphs $SG_{2s,4}$ are test graphs, i.e. for every graph $H$ and $r \geq 0$ such that $\mathrm{Hom}(SG_{2s,4},H)$ is $(r-1)$-connected, the chromatic number $\chi (H)$ is at least $r+6$. On the other hand, if $k \notin \{0,1,2,4,8\}$ and $n \geq N(k)$ then $SG_{n,k}$ is not a homotopy test graph, i.e. there are a graph $G$ and an $r \geq 1$ such that $\mathrm{Hom}(SG_{n,k}, G)$ is $(r-1)$-connected and $\chi (G) < r+k+2$. The latter result also depends on a new necessary criterion for being a test graph, which involves the automorphism group of the graph.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01215058
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Tuesday, October 13, 2015 - 3:05:50 PM
Last modification on : Thursday, January 6, 2022 - 12:14:04 PM
Long-term archiving on: : Thursday, April 27, 2017 - 12:18:34 AM

File

dmAO0176.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Carsten Schultz. The equivariant topology of stable Kneser graphs. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.873-884, ⟨10.46298/dmtcs.2960⟩. ⟨hal-01215058⟩

Share

Metrics

Record views

73

Files downloads

427