Small models of graph colouring manifolds and the Stiefel manifolds (C₅,K_n)

DOI10.1016/J.JCTA.2007.04.004MaRDI QIDQ2469199zbMATH OpenOpenAlexFDO

Authors Carsten A. Schultz

Publication date 4 February 2008

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

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

zbMATH Keywords

graph coloringsgraph complexesgraph homomorphismHom-complexesmanifoldsposetsubdivision

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Relations of low-dimensional topology with graph theory (57M15) Triangulating manifolds (57Q15)

Abstract: We show P'eter Csorba's conjecture that the graph homomorphism complex Hom(C_5,K_{n+2}) is homeomorphic to a Stiefel manifold, the space of unit tangent vectors to the n-dimensional sphere. For this a general tool is developed that allows to replace the complexes Hom(G, K_n) by smaller complexes that are homeomorphic to them whenever G is a graph for which those complexes are manifolds. The equivariant version of Csorba's conjecture is proved up to homotopy. We also study certain subdivisions of simplicial manifolds that are related to the interval poset of their face posets and their connection with geometric approximations to diagonal maps.

Review text

The main result of this article is the following: The graph homomorphism complex \(\Hom(C_5, K_{n+2})\) is homeomorphic with the space of all unit tangent vectors on the \(n\)-sphere \(S^n\). This settles a conjecture made by \textit{P. Csorba} in his PhD thesis at ETH Zürich 2005. In particular these Hom complexes are manifolds. Other cases where Hom complexes are manifolds were studied by \textit{P. Cscorba} and \textit{F. H. Lutz} in a paper reviewed in [Graph coloring manifolds, Contemporary Mathematics 423, 51--69 (2006; Zbl 1121.05046)]. An important tool in proving this result is to replace the full Hom complexes by smaller complexes of type \(\Hom_I(C_5,K_{n+2})\) where \(I\) denotes an independent set of vertices in the graph. This method works if the Hom complex is a manifold.

Recommendations

• Stiefel manifolds and coloring the pentagon
• Complexes of graph homomorphisms
• Graph coloring manifolds
• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
• Proof of the Lovász conjecture

Cites work

• A simple proof for folds on both sides in complexes of graph homomorphisms
• Box complexes, neighborhood complexes, and the chromatic number
• Canonical homeomorphisms of posets
• Classifying spaces and spectral sequences
• Complexes of graph homomorphisms
• Graph coloring manifolds
• Homotopy types of box complexes
• scientific article; zbMATH DE number 3749892 (Why is no real title available?)
• scientific article; zbMATH DE number 3340089 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• Proof of the Lovász conjecture
• Topological lower bounds for the chromatic number: a hierarchy
• Unknotting combinatorial balls
• WI-posets, graph complexes and \(\mathbb{Z}_2\)-equivalences

Cited in

(8)

• Graph colorings, spaces of edges and spaces of circuits
• Homomorphism complexes and maximal chains in graded posets
• Using equivariant obstruction theory in combinatorial geometry
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• Stiefel manifolds and coloring the pentagon
• The equivariant topology of stable Kneser graphs
• Homomorphism complexes and \(k\)-cores
• A short proof of \(w_{1}^n (\text{Hom}(C_{2r+1}, K_{n+2})) = 0\) for all \(n\) and a graph colouring theorem by Babson and Kozlov

This page was built for publication: Small models of graph colouring manifolds and the Stiefel manifolds \(\Hom(C_{5},K_n)\)

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