Hom complexes and homotopy theory in the category of graphs

DOI10.1016/J.EJC.2008.04.009MaRDI QIDQ1003603zbMATH OpenOpenAlexFDO

Authors Anton Dochtermann

Publication date 4 March 2009

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

equivalencecategory of graphsgraph maphomotopydismantlableA-homotopyfolds of graphsHom complex

Mathematics Subject Classification ID

Partial orders, general (06A06) Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorics and topology in relation with holomorphic dynamical systems (37F20) PL-topology (57Q99)

Abstract: We investigate a notion of $imes$-homotopy of graph maps that is based on the internal hom associated to the categorical product in the category of graphs. It is shown that graph $imes$-homotopy is characterized by the topological properties of the $Hom$ complex, a functorial way to assign a poset (and hence topological space) to a pair of graphs; $Hom$ complexes were introduced by Lov'{a}sz and further studied by Babson and Kozlov to give topological bounds on chromatic number. Along the way, we also establish some structural properties of $Hom$ complexes involving products and exponentials of graphs, as well as a symmetry result which can be used to reprove a theorem of Kozlov involving foldings of graphs. Graph $imes$-homotopy naturally leads to a notion of homotopy equivalence which we show has several equivalent characterizations. We apply the notions of $imes$-homotopy equivalence to the class of dismantlable graphs to get a list of conditions that again characterize these. We end with a discussion of graph homotopies arising from other internal homs, including the construction of `$A$-theory' associated to the cartesian product in the category of reflexive graphs.

Recommendations

• Hom complexes and homotopy in the category of graphs
• Homotopy groups of Hom complexes of graphs
• Homotopy types of the Hom complexes of graphs
• Complexes of graph homomorphisms
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 2186305 (Why is no real title available?)
• scientific article; zbMATH DE number 1226952 (Why is no real title available?)
• scientific article; zbMATH DE number 2151248 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• A simple proof for folds on both sides in complexes of graph homomorphisms
• Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
• Collapsing along monotone poset maps
• Complexes of graph homomorphisms
• Gibbs measures and dismantlable graphs
• Homotopical algebra
• Homotopy groups of Hom complexes of graphs
• Homotopy theory of graphs
• Kneser's conjecture, chromatic number, and homotopy
• On the complexity of H-coloring
• Perspectives on \(A\)-homotopy theory and its applications
• Proof of the Lovász conjecture
• Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes

Cited in

(58)

• Dominance complexes, neighborhood complexes and combinatorial Alexander duals
• Discrete-to-continuous extensions: Lovász extension and Morse theory
• Spider web graphs
• Strong digital topological complexity of digital maps
• Connectedness of certain graph coloring complexes
• Homotopy, homology, and persistent homology using closure spaces
• Nonexistence of colimits in naive discrete homotopy theory
• Closed symmetric monoidal structures on the category of graphs
• The fundamental group in discrete homotopy theory
• Graph homotopy and Graham homotopy
• Strong homotopy induced by adjacency structure
• The discrete fundamental group of the order complex of \(B_n\)
• A homotopy category for graphs
• A simple proof for folds on both sides in complexes of graph homomorphisms
• Homotopy and Hom construction in the category of finite hypergraphs
• Cospan construction of the graph category of Borisov and Manin
• \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture
• Square-free graphs are multiplicative
• scientific article; zbMATH DE number 5990556 (Why is no real title available?)
• scientific article; zbMATH DE number 7499158 (Why is no real title available?)
• Fundamental groupoids for graphs
• Neighborhood complexes of some exponential graphs
• A topological lower bound for the chromatic number of a special family of graphs
• Box complexes and homotopy theory of graphs
• Settings and misunderstandings in mathematics
• Homology of \(\operatorname{Hom}\) complexes
• Higher hairy graph homology
• Morphism complexes of sets with relations
• Digital topological groups
• Foldings in graphs and relations with simplicial complexes and posets
• Topology of Hom complexes and test graphs for bounding chromatic number
• The universality of Hom complexes of graphs
• Graphs, foams, tensors, polytopes, and homology
• Shannon capacity and the categorical product
• Hom complexes and homotopy in the category of graphs
• Warmth and edge spaces of graphs
• The neighborhood complex of a random graph
• Altermatic number of categorical product of graphs
• Homotopy groups of Hom complexes of graphs
• Mixing homomorphisms, recolorings, and extending circular precolorings
• On topological relaxations of chromatic conjectures
• Minimal graphs for contractible and dismantlable properties
• Homomorphism reconfiguration via homotopy
• Paths of homomorphisms from stable Kneser graphs
• Neighborhood complexes, homotopy test graphs and an application to coloring of product graphs
• On the Simple ℤ₂-homotopy Types of Graph Complexes and Their Simple ℤ₂-universality
• Hedetniemi's conjecture for Kneser hypergraphs
• The equivariant topology of stable Kneser graphs
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• Equivariant collapses and the homotopy type of iterated clique graphs
• Aspects of topological approaches for data science
• \(s\)-homotopy for finite graphs
• Hedetniemi's conjecture and strongly multiplicative graphs
• Homotopy types of the Hom complexes of graphs
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs
• (Lack of) model structures on the category of graphs
• Graph homology: Koszul and Verdier duality
• Homotopy type of circle graph complexes motivated by extreme Khovanov homology

This page was built for publication: Hom complexes and homotopy theory in the category of graphs

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