Box complexes and homotopy theory of graphs
Let \(G\) be a graph. The neighborhood complex \(N(G)\) was introduced for the proof of Kneser's conjecture. The box complex \(B(G)\) is a \(\mathbb{Z}_2\)-space which is homotopy equivalent to \(N(G)\). Let \(T\) and \(G\) be two graphs. The Hom complex \(\mathrm{Hom}(T,G)\) is a cell complex which is a higher-dimensional generalization of the box complex. Moreover, let \(\Gamma\) be a group. If \(T\) is a right \(\Gamma\)-graph, then \(\mathrm{Hom}(T,G)\) is a left \(\Gamma\)-space, and a graph homomorphism \(f:G_1\to G_2\) induces a \(\Gamma\)-map \(f_*: \mathrm{Hom}(T, G_1) \to \mathrm{Hom}(T, G_2)\). The group actions on Hom complexes can be used to construct obstructions for graph coloring problems. Let \(\Gamma\) be a finite group and \(T\) be a finite right \(\Gamma\)-graph. In a previous paper of the author, a singular complex functor was constructed \(\mathrm{Sing}_T : \mathcal{G} \to \mathrm{SSet}^\Gamma\), sending a graph \(G\) to a simplicial set \(\mathrm{Sing}(T,G)\). Here \(\mathcal{G}\) is the category of graphs, and \(\mathrm{SSet}^\Gamma\) is the category of \(\Gamma\)-simplicial sets. The author proved in a previous paper that there is a natural homotopy equivalence \(|\mathrm{Sing}(T,G)| \to |\mathrm{Hom}(T,G)|\). Since \(\mathrm{Hom}(T,G)\) is not a simplicial complex nor a simplicial set, the construction \(\mathrm{Sing}(T,G)\) improves the construction of \(\mathrm{Hom}(T,G)\). In this paper, the author considers some functors and their relations with the Hom complexes. Let \(A_T\) denote the left adjoint of \(\mathrm{Sing}_T\). Consider the unit of the adjoint pair \(A_T \circ \mathrm{Sd}^k \circ \mathrm{Ex}^k \circ \mathrm{Sing}_T : \mathrm{SSet}^\Gamma \to \mathcal{G}\). Here Sd is the barycentric subdivision functor and Ex is Kan's extension functor. The author takes \(k\) to be sufficiently large. The author considers two properties of the Hom complex stated as (A) and (B). Then the author uses the unit of the adjoint pair \(A_T \circ \mathrm{Sd}^k \circ \mathrm{Ex}^k \circ \mathrm{Sing}_T\) to give some equivalent characterizations of (A) and (B). The main results are Theorem 1.1 (Theorem 3.4) and Theorem 1.2 (Theorem 3.5).
- Box complexes, neighborhood complexes, and the chromatic number
- A homotopy category for graphs
- (Lack of) model structures on the category of graphs
- \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture
- Homomorphism complexes, reconfiguration, and homotopy for directed graphs
- Graphs, foams, tensors, polytopes, and homology
- Fundamental groupoids for graphs
- Simplicial approximation and refinement of monoidal topological complexity
- Topology and Adjunction in Promise Constraint Satisfaction
- Homotopy and Hom construction in the category of finite hypergraphs
- Thomason-type model structures on simplicial complexes and graphs
- Homotopy covers of graphs
- Homotopy types of box complexes of chordal graphs
- The universality of Hom complexes of graphs
This page was built for publication: Box complexes and homotopy theory of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1689736)
