The equivariant topology of stable Kneser graphs

DOI10.1016/J.JCTA.2011.04.009MaRDI QIDQ640844zbMATH OpenOpenAlexFDO

Authors Carsten A. Schultz

Publication date 21 October 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.5688

zbMATH Keywords

graph homomorphismstable Kneser graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: The stable Kneser graph $S{G}_{n,k}$, $nge1$, $kge0$, 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"orner and de Longueville cite{anders-mark} have shown that its box complex is homotopy equivalent to a sphere, $Hom(K_2,S{G}_{n,k})homotSpher{e}^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}imes{D}_{2m})$-homotopy type of $Hom(K_2,S{G}_{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 $rge0$ such that $Hom(S{G}_{2s,4},H)$ is $(r-1)$-connected, the chromatic number $chi(H)$ is at least $r+6$. If $kotinset0,1,2,4,8$ and $ngeN(k)$ then $S{G}_{n,k}$ is not a homotopy test graph, i.e. there are a graph $G$ and an $rge1$ such that $Hom(S{G}_{n,k},G)$ is $(r-1)$-connected and $chi(G)<r+k+2$.

Review text

The stable Kneser graph \(SG_{n,k}\) (where \(n\) and \(k\) are integers satisfying \(n\geq 1\) and \(k\geq 0\)) is a vertex critical graph with chromatic number \(k+2\). It ist also called the Schrijver graph. Lovasz considered a cell complex \(\Hom(H, G)\) for given graphs \(G\) and \(H\) where the vertices of \(\Hom(H, G)\) are the graph homomorphisms from \(H\) to \(G\). A graph \(T\) is called a homotopy test graph if for all loopless graphs \(G\) and \(r\geq 0\) such that \(\Hom(G, T)\) is \((r-1)\) connected \(\chi(g)\geq\chi(T)+ r\) holds. In the present paper it is shown that the graphs \(SG_{2s,4}\) are homotopy test graphs and that \(SG_{n,k}\) is not a homotopy test graph if \(k\not\in\{0,1,2,4,8\}\) and \(n\geq N(k)\).

Recommendations

• The equivariant topology of stable Kneser graphs
• scientific article; zbMATH DE number 2186841
• Stable cohomology of graph complexes
• Shifts of the stable Kneser graphs and hom-idempotence
• Paths of homomorphisms from stable Kneser graphs
• Equivariant de Rham theory and graphs
• scientific article; zbMATH DE number 2107948
• Neighborhood complexes of stable Kneser graphs
• Equivariant stable homotopy theory and the Kervaire invariant problem
• Khovanov type homologies for graphs

Cites work

• A combinatorical proof of Kneser's conjecture
• A counterexample to a conjecture of Björner and Lovász on the \(\chi\)-coloring complex
• A short proof of Kneser's conjecture
• Characteristic Classes. (AM-76)
• Complexes of graph homomorphisms
• Generalized Kneser coloring theorems with combinatorial proofs
• Graph colorings, spaces of edges and spaces of circuits
• Groups of homotopy spheres. I
• Hom complexes and homotopy theory in the category of graphs
• Homotopy equivalence of posets with a group action
• Homotopy types of box complexes
• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• scientific article; zbMATH DE number 2016544 (Why is no real title available?)
• scientific article; zbMATH DE number 3233464 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• Neighborhood complexes of stable Kneser graphs
• Oriented Matroids
• Proof of the Lovász conjecture
• Small models of graph colouring manifolds and the Stiefel manifolds \(\Hom(C_{5},K_n)\)
• Symmetries of the stable Kneser graphs
• The universality of Hom complexes of graphs
• Topology of Hom complexes and test graphs for bounding chromatic number
• User's guide to equivariant methods in combinatorics. II

Cited in

(17)

• The neighborhood complexes of almost \(s\)-stable Kneser graphs
• A topological lower bound for the chromatic number of a special family of graphs
• Topology of Hom complexes and test graphs for bounding chromatic number
• Neighborhood complexes of stable Kneser graphs
• Homotopy types of the Hom complexes of graphs
• On the neighborhood complex of \(\overrightarrow{s} \)-stable Kneser graphs
• Neighborhood complexes, homotopy test graphs and an application to coloring of product graphs
• The equivariant topology of stable Kneser graphs
• Answers to some problems about graph coloring test graphs
• Paths of homomorphisms from stable Kneser graphs
• Shifts of the stable Kneser graphs and hom-idempotence
• Deformation retracts of neighborhood complexes of stable Kneser graphs
• Independence complexes of stable Kneser graphs
• Connectedness of certain graph coloring complexes
• Hom complexes of graphs whose codomains are square-free
• A special case of the stahl conjecture
• Box complexes: at the crossroad of graph theory and topology

This page was built for publication: The equivariant topology of stable Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q640844)