Hom complexes and homotopy theory in the category of graphs

DOI10.1016/J.EJC.2008.04.009zbMATH Open1167.05017arXivmath/0605275OpenAlexW2109978147MaRDI QIDQ1003603FDOQ1003603

Authors: Anton Dochtermann 

Publication date: 4 March 2009

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

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.

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

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

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)

Cites Work

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

Cited In (58)

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

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)