Séminaire Lotharingien de Combinatoire, 86B.7 (2022), 12 pp.
Anton Dochtermann and Anurag Singh
Homomorphism Complexes, Reconfiguration,
and Homotopy for Directed Graphs
Abstract.
The neighborhood complex of a graph was introduced by Lov\'asz to provide topological lower bounds on chromatic number, and more general homomorphism complexes of graphs were further studied by Babson and Kozlov. Such `Hom complexes' are also related to reconfiguration problems as well as a notion of discrete homotopy. Here we initiate the detailed study of Hom complexes for directed graphs (digraphs). For any pair of digraphs G and H we consider the polyhedral complex Hom->(G,H) that parametrizes the digraph homomorphisms f : G -> H. Such complexes have applications in the study of chains in graded posets and cellular resolutions of monomial ideals.
We study topological properties of Hom-> complexes and relate them to graph operations including products, adjunctions, and foldings. We introduce the notion of the neighborhood complex of a digraph and establish several properties regarding its topology, including its homotopy type as a Hom-> complex, dependence on directed bipartite subgraphs, and vanishing theorems for higher homology. Inspired by the notion of reconfiguration for digraph colorings we study the connectivity of Hom->(G,Tn) for Tn a tournament, obtaining a complete answer for the case of transitive Tn. Finally we use paths in the internal hom objects of directed graphs to define various notions of homotopy, and discuss connections to the topology of Hom-> complexes.
Received: November 25, 2021.
Accepted: March 4, 2022.
Final version: April 1, 2022.
The following versions are available: