2023/05/04 by Delia Garijo, Garijo, Delia, Andrew Goodall +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Dynamics and Fractals #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2305.03107
openalex publication_date 2023/05/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We extend the notion of graph homomorphism to cellularly embedded graphs (maps) by designing operations on vertices and edges that respect the surface topology; we thus obtain the first definition of map homomorphism that preserves both the combinatorial structure (as a graph homomorphism) and the topological structure of the surface (in particular, orientability and genus). Notions such as the core of a graph and the homomorphism order on cores are then extended to maps. We also develop a purely combinatorial framework for various topological features of a map such as the contractibility of closed walks, which in particular allows us to characterize map cores. We then show that the poset of map cores ordered by the existence of a homomorphism is connected and, in contrast to graph homomorphisms, does not contain any dense interval (so it is not universal for countable posets). Finally, we give examples of a pair of cores with an infinite number of cores between them, an infinite chain of gaps, and arbitrarily large antichains with a common homomorphic image.