pith. sign in

arxiv: 2606.09231 · v1 · pith:6KULU65Wnew · submitted 2026-06-08 · 🧮 math.CO

Constrained homomorphism orders

classification 🧮 math.CO
keywords homomorphismsfinitelocallyconstrainedcoresgraphshomomorphismorders
0
0 comments X
read the original abstract

We study partial orders induced by constrained variants of finite graph homomorphisms: monomorphisms, embeddings, full homomorphisms, vertex-surjective, edge-surjective and surjective homomorphisms, and locally injective, locally surjective and locally bijective homomorphisms. For each order we ask for analogues of the standard structural properties of the graph homomorphism order: canonical cores, past- or future-finiteness, universality, gaps and finite dualities. The comparison shows which phenomena are specific to ordinary homomorphisms and which are consequences of simpler order-theoretic mechanisms. We identify cores for full and surjective homomorphisms, relate full-homomorphism cores to point-determining graphs, characterize gaps in the full homomorphism order, and give finite obstruction bounds for several one-sided finite orders. We also analyze locally constrained homomorphisms on connected graphs. In particular, locally injective homomorphisms have all connected graphs as cores, admit infinite-chain density under natural degree-refinement assumptions, have explicit gap witnesses, and are universal already on finite connected bipartite subcubic cactus graphs. The paper reorganizes and extends several earlier arguments into a single framework for constrained homomorphism orders.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.