Homotopy covers of graphs
Abstract
We develop a theory of ×-homotopy, fundamental groupoids and covering spaces that applies to non-simple graphs, generalizing existing results for simple graphs. We prove that ×-homotopies from finite graphs can be decomposed into moves that adjust at most one vertex at a time, generalizing the spider lemma of Chih & Scull (2021). We define a notion of homotopy covering map and develop a theory of universal covers and deck transformations, generalizing Matsushita (2017) and Tardif–Wroncha (2019) to non-simple graphs. We examine the case of reflexive graphs (each vertex having at least one loop). We also prove that these homotopy covering maps satisfy a homotopy lifting property for arbitrary graph homomorphisms, generalizing path lifting results of Matsushita and Tardif–Wroncha.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2026.14.1.1
References
D. Angluin, Local and global properties in networks of processors (extended abstract), Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing (1980), 82-93.
D. Angluin and A. Gardiner, Finite common coverings of pairs of regular graphs, J. Combin. Theory Ser. B, 30 (1981), 184-187.
E. Babson, H. Barcelo, M. de Longueville, and R. Laubenbacher, Homotopy theory of graphs, J. Algebraic Combin., 24 (2006), 31-44.
E. Babson, and D. Kozlov, Complexes of graph homomorphisms, Israel J. Math., 152 (2006), 285-312.
H. Barcelo, X. Kramer, R. Laubenbacher, and C. Weaver, Foundations of a connectivity theory for simplicial complexes, Adv. Appl. Math., 26 (2001), 97-128.
H. Bass, Covering theory for graphs of groups, J. Pure Appl. Algebra, 89 (1993), 3-47.
M. Bridson and S. Shepherd, Leighton's theorem: Extensions, limitations and quasitrees, Algebr. Geom. Topol., 22 (2022), 881-917.
T. Chih and L. Scull, A homotopy category for graphs, J. Algebraic Combin., 53 (2021), 1231-1251.
T. Chih and L. Scull, Fundamental groupoids for graphs, Categ. Gen. Algebr. Struct. Appl., 16 (2022), 221-248.
A. Dochtermann, Hom complexes and homotopy theory in the category of graphs, European J. Combin., 30 (2009), 490-509.
A. Dochtermann, Homotopy groups of hom complexes of graphs, J. Combin. Theory Ser. A, 116 (2009), 180-194.
A. Hatcher, Algebraic Topology, Cambridge University Press, 2001.
P.J. Higgins, Categories and groupoids, Repr. Theory Appl. Categ., 7 (2005).
D. Kozlov, Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes, Geometric Combinatorics IAS/Park City Math. Ser., 14 (2005).
D. Kozlov, Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes, Topology Appl., 14 (2006) 2445-2454.
D. Kozlov, A simple proof for folds on both sides in complexes of graph homomorphisms, Proc. Amer. Math. Soc., 134 (2006) 1265-1270.
J. Kwak and R. Nedela, Graphs and Their Coverings, (2005).
F. Leighton, Finite common coverings of graphs, J. Combin. Theory Ser. B, 33 (1982) 231-238.
T. Matsushita, Box complexes and homotopy theory of graphs, Homology Homotopy Appl., 19 (2017) 175-197.
T. Matsushita, Fundamental groups of neighborhood complexes, J. Math. Sci. Univ. Tokyo, 24 (2017) 321-353.
R.H. Morrill, The lifting properties of A-homotopy theory, Contrib. Discrete Math., 19 (2024) 36-67.
M. Sankar, Homotopy and the homomorphism threshold of odd cycles, (2022) arXiv:2206.07525.
S. Shepherd, Two generalisations of Leighton's theorem (with an appendix by Giles Gardam and Daniel J. Woodhouse), Groups Geom. Dyn., 16 (2022) 2218-2250.
T. Tardif and M. Wroncha, Hedetniemi's conjecture and strongly multiplicative graphs, SIAM J. Discrete Math., 33 (2019) 2218-2250.
D. Woodhouse, Leighton's theorem and regular cube complexes, Algebra. Geom. Topol., 23 (2023) 3395-3415.
D. Woodhouse, Revisiting Leighton's theorem with the Haar measure, Math. Proc. Cambridge Philos. Soc., 170 (2024) 615-623.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.