pith. sign in

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

Constrained homomorphism orders

Jiri Fiala , Jan Hubicka , Yangjing Long This is my paper

Pith reviewed 2026-06-27 16:20 UTC · model grok-4.3

classification 🧮 math.CO
keywords graph homomorphism ordersconstrained homomorphismsgraph coreshomomorphism gapslocally injective homomorphismspoint-determining graphsuniversalityfinite dualities
0
0 comments X

The pith

Constrained graph homomorphisms admit cores, gaps, and universality properties analogous to the standard homomorphism order.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines partial orders on graphs created by constrained homomorphisms including monomorphisms, full homomorphisms, surjective variants, and locally injective or bijective ones. It determines that cores exist for full and surjective homomorphisms and links full-homomorphism cores directly to point-determining graphs. Gaps receive an explicit characterization in the full homomorphism order, while several one-sided finite orders obtain finite obstruction bounds. Locally injective homomorphisms turn every connected graph into a core, support infinite-chain density under degree-refinement conditions, supply explicit gap witnesses, and achieve universality already when restricted to finite connected bipartite subcubic cactus graphs. These results separate order-theoretic mechanisms from features unique to ordinary homomorphisms.

Core claim

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. 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.

What carries the argument

The partial orders induced by each constrained homomorphism relation, with cores as the minimal elements under the induced order.

If this is right

  • Full-homomorphism cores coincide exactly with point-determining graphs.
  • Gaps in the full homomorphism order admit an explicit characterization.
  • Several one-sided finite constrained orders possess finite obstruction bounds.
  • Locally injective homomorphisms make every connected graph a core and remain universal on finite connected bipartite subcubic cactus graphs.
  • Locally constrained homomorphisms on connected graphs exhibit infinite-chain density under degree-refinement assumptions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same transfer of properties may hold for additional constrained relations not examined here.
  • Universality on cactus graphs indicates that homomorphism problems under local injectivity become tractable on this restricted class.
  • Gap characterizations could extend to deciding density or rigidity questions in the corresponding orders.
  • A unified framework may allow direct comparison of homomorphism orders with orders induced by other relational constraints such as those on hypergraphs.

Load-bearing premise

The structural properties of cores, gaps, and universality transfer from ordinary homomorphisms to the constrained versions by the same order-theoretic mechanisms once the relation is replaced.

What would settle it

A connected graph that fails to be a core under locally injective homomorphisms, or a gap in the full homomorphism order outside the claimed characterization.

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript examines the partial orders arising from constrained graph homomorphisms, including monomorphisms, embeddings, full homomorphisms, vertex- and edge-surjective homomorphisms, surjective homomorphisms, and locally injective, surjective, and bijective homomorphisms. For each such order, it investigates analogues of key properties from the standard graph homomorphism order, such as the existence of canonical cores, past- or future-finiteness, universality, the presence of gaps, and finite dualities. The authors provide specific results including the identification of cores for full and surjective homomorphisms and their relation to point-determining graphs, a characterization of gaps in the full homomorphism order, finite obstruction bounds for one-sided finite orders, and detailed analysis for locally constrained homomorphisms on connected graphs, notably that locally injective homomorphisms have all connected graphs as cores, exhibit infinite-chain density under degree-refinement assumptions, possess explicit gap witnesses, and are universal even when restricted to finite connected bipartite subcubic cactus graphs.

Significance. If the results hold, the paper supplies a uniform framework that isolates which structural features of homomorphism orders are intrinsic to the homomorphism relation itself versus those that follow from general order-theoretic mechanisms. The explicit core identifications, gap characterizations, and the universality result for locally injective homomorphisms already on finite connected bipartite subcubic cactus graphs constitute concrete advances that reorganize and extend earlier arguments while furnishing falsifiable structural statements.

minor comments (1)
  1. The abstract states that the work 'reorganizes and extends several earlier arguments'; a short dedicated paragraph in the introduction listing the precise prior results being unified would improve traceability for readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their detailed summary of the manuscript and for recommending acceptance. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; claims are direct structural results

full rationale

The paper presents explicit identifications of cores for constrained homomorphisms, gap characterizations, finite obstruction bounds, and universality results on restricted classes as direct extensions of order-theoretic mechanisms. No equations, fitted parameters, or predictions appear; the abstract and description frame results as reorganizations of prior arguments into a uniform framework without reducing any central claim to a self-citation chain or definitional equivalence. The transfer of properties is stated as an assumption but does not manifest as a load-bearing circular step in the supplied material. This is a standard self-contained mathematical analysis in graph theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard definitions of graphs and the listed homomorphism variants; no free parameters, ad-hoc axioms, or invented entities are mentioned in the abstract.

axioms (2)
  • standard math Standard definitions of graphs, homomorphisms, and the nine constrained variants (monomorphisms, embeddings, full, vertex-surjective, edge-surjective, surjective, locally injective, locally surjective, locally bijective).
    Invoked throughout the abstract when defining the orders.
  • domain assumption The partial orders induced by these relations on the class of all finite graphs admit the listed structural properties (cores, gaps, universality, finite dualities).
    The central comparison assumes these properties can be meaningfully asked and answered for each variant.

pith-pipeline@v0.9.1-grok · 5717 in / 1529 out tokens · 19497 ms · 2026-06-27T16:20:32.902093+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

50 extracted references · 26 canonical work pages

  1. [1]

    Oxford lecture series in mathematics and its applications

    Hell, P., Nešetřil, J.: Graphs and Homomorphisms. Oxford lecture series in mathematics and its applications. Oxford University Press, Oxford (2004). http: //books.google.de/books?id=bJXWV-qK7kYC

    2004

  2. [2]

    North-Holland mathematical library

    Pultr, A., Trnková, V.: Combinatorial, Algebraic, and Topological Represen- tations of Groups, Semigroups, and Categories. North-Holland mathematical library. North-Holland Publishing Company, Amsterdam (1980). http://books. google.de/books?id=uyDMgbpXGY8C

    1980

  3. [3]

    Journal of Combinatorial Theory, Series B80(1), 80–97 (2000) https://doi.org/10.1006/jctb.2000.1970

    Nešetřil, J., Tardif, C.: Duality theorems for finite structures (characterising gaps and good characterisations). Journal of Combinatorial Theory, Series B80(1), 80–97 (2000) https://doi.org/10.1006/jctb.2000.1970

    work page doi:10.1006/jctb.2000.1970 2000

  4. [4]

    European Journal of Combinatorics26(5), 765–778 (2005) https://doi.org/10.1016/j.ejc.2004.01.008

    Hubička, J., Nešetřil, J.: Universal partial order represented by means of oriented trees and other simple graphs. European Journal of Combinatorics26(5), 765–778 (2005) https://doi.org/10.1016/j.ejc.2004.01.008

    work page doi:10.1016/j.ejc.2004.01.008 2005

  5. [5]

    Order21(3), 181–200 (2004) https://doi.org/10.1007/s11083-004-3345-9

    Hubička, J., Nešetřil, J.: Finite paths are universal. Order21(3), 181–200 (2004) https://doi.org/10.1007/s11083-004-3345-9

    work page doi:10.1007/s11083-004-3345-9 2004

  6. [6]

    European Journal of Combinatorics 29(2), 493–506 (2008) https://doi.org/10.1016/j.ejc.2007.02.005

    Lehtonen, E.: Labeled posets are universal. European Journal of Combinatorics 29(2), 493–506 (2008) https://doi.org/10.1016/j.ejc.2007.02.005

    work page doi:10.1016/j.ejc.2007.02.005 2008

  7. [7]

    European Jour- nal of Combinatorics29(4), 881–899 (2008) https://doi.org/10.1016/j.ejc.2007

    Foniok, J., Nešetřil, J., Tardif, C.: Generalised dualities and maximal finite antichains in the homomorphism order of relational structures. European Jour- nal of Combinatorics29(4), 881–899 (2008) https://doi.org/10.1016/j.ejc.2007. 11.017

    work page doi:10.1016/j.ejc.2007 2008

  8. [8]

    arXiv preprint arXiv:2212.13313 (2023) https://doi.org/10.48550/arXiv.2212.13313

    Guzmán-Pro, S.: Full-homomorphisms to paths and cycles. arXiv preprint arXiv:2212.13313 (2023) https://doi.org/10.48550/arXiv.2212.13313

    work page doi:10.48550/arxiv.2212.13313 2023

  9. [9]

    ACM Transactions on Computation Theory11(1), 3 (2019) https: //doi.org/10.1145/3282431

    Larose, B., Martin, B., Paulusma, D.: SurjectiveH-colouring over reflexive digraphs. ACM Transactions on Computation Theory11(1), 3 (2019) https: //doi.org/10.1145/3282431 . Article 3, 21 pp

    work page doi:10.1145/3282431 2019

  10. [10]

    SIAM Journal on Discrete Mathematics33(2), 1006–1043 (2019) https://doi.org/10.1137/17M1153182

    Focke, J., Goldberg, L.A., Živný, S.: The complexity of counting surjective homo- morphisms and compactions. SIAM Journal on Discrete Mathematics33(2), 1006–1043 (2019) https://doi.org/10.1137/17M1153182

    work page doi:10.1137/17m1153182 2019

  11. [11]

    Compu- tationalComplexity33(1),7(2024)https://doi.org/10.1007/s00037-024-00253-4

    Chen, H.: Algebraic global gadgetry for surjective constraint satisfaction. Compu- tationalComplexity33(1),7(2024)https://doi.org/10.1007/s00037-024-00253-4

    work page doi:10.1007/s00037-024-00253-4 2024

  12. [12]

    SIAM Jour- nal on Discrete Mathematics38(2), 1315–1350 (2024) https://doi.org/10.1137/ 22M1513290

    Bulteau, L., Dabrowski, K.K., Köhler, N., Ordyniak, S., Paulusma, D.: An algorithmic framework for locally constrained homomorphisms. SIAM Jour- nal on Discrete Mathematics38(2), 1315–1350 (2024) https://doi.org/10.1137/ 22M1513290

    2024

  13. [13]

    In: 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

    Dvořák, P., Masařík, T., Novotná, J., Krawczyk, M., Rzążewski, P., Żuk, A.: List Locally Surjective Homomorphisms in Hereditary Graph Classes. In: 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leib- niz International Proceedings in Informatics (LIPIcs), vol. 248, p. 30. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl...

    work page doi:10.4230/lipics.isaac.2022.30 2022

  14. [14]

    Kratochvíl, J., Nedela, R.: Graph covers and semi-covers: Who is stronger? arXiv preprint arXiv:2504.17387 (2025) https://doi.org/10.48550/arXiv.2504.17387 29

    work page doi:10.48550/arxiv.2504.17387 2025

  15. [15]

    Fiala, J

    Fiala, J., Hubička, J., Long, Y.: An universality argument for graph homomor- phisms. Electronic Notes in Discrete Mathematics49, 643–649 (2015) https: //doi.org/10.1016/j.endm.2015.06.087

    work page doi:10.1016/j.endm.2015.06.087 2015

  16. [16]

    Why do many resource-rich countries have negative genuine saving? Anticipation of better times or rapacious rent seeking.Resource and Energy Economics, 32(1):28–44, 2010

    Fiala, J., Hubička, J., Long, Y.: Gaps in full homomorphism order. Electronic Notes in Discrete Mathematics61, 429–435 (2017) https://doi.org/10.1016/j. endm.2017.06.070

    work page doi:10.1016/j 2017

  17. [17]

    European Journal of Combinatorics41, 221–231 (2014)

    Fiala, J., Hubička, J., Long, Y.: Universality of intervals of line graph order. European Journal of Combinatorics41, 221–231 (2014)

    2014

  18. [18]

    European Journal of Combinatorics66, 101–109 (2017)

    Fiala, J., Hubička, J., Long, Y., Nešetřil, J.: Fractal property of the graph homomorphism order. European Journal of Combinatorics66, 101–109 (2017)

    2017

  19. [19]

    In: Grohe, M., Makowsky, J.A

    Hubička, J., Nešetřil, J.: Some examples of universal and generic partial orders. In: Grohe, M., Makowsky, J.A. (eds.) Model Theoretic Methods in Finite Combinatorics, pp. 293–318. American Mathematical Society, Providence, RI (2011)

    2011

  20. [20]

    Hedrlín, Z.: On universal partly ordered sets and classes. J. Algebra11(4), 503– 509 (1969)

    1969

  21. [21]

    Journal of Mathematical Physics 46(12), 10 (2005) https://doi.org/10.1063/1.2147607

    Droste, M.: Universal homogeneous causal sets. Journal of Mathematical Physics 46(12), 10 (2005) https://doi.org/10.1063/1.2147607

    work page doi:10.1063/1.2147607 2005

  22. [22]

    Euro- pean Journal of Combinatorics27(7), 1159–1171 (2006) https://doi.org/10.1016/ j.ejc.2006.06.012

    Nešetřil, J., Nigussie, Y.: Minimal universal and dense minor closed classes. Euro- pean Journal of Combinatorics27(7), 1159–1171 (2006) https://doi.org/10.1016/ j.ejc.2006.06.012

    2006

  23. [23]

    European Journal of Combinatorics 31(8), 1981–1995 (2010)

    Lehtonen, E., Nešetřil, J.: Minors of boolean functions with respect to clique functions and hypergraph homomorphisms. European Journal of Combinatorics 31(8), 1981–1995 (2010)

    1981

  24. [24]

    Order 28(2), 251–265 (2011) https://doi.org/10.1007/s11083-010-9169-x

    Kwuida, L., Lehtonen, E.: On the homomorphism order of labeled posets. Order 28(2), 251–265 (2011) https://doi.org/10.1007/s11083-010-9169-x

    work page doi:10.1007/s11083-010-9169-x 2011

  25. [25]

    In: Nešetřil, J., Pel- legrini, M

    Šámal, R.: Cycle-continuous mappings — order structure. In: Nešetřil, J., Pel- legrini, M. (eds.) The Seventh European Conference on Combinatorics, Graph Theory and Applications. CRM Series, vol. 16, pp. 513–520. Scuola Normale Superiore, Pisa (2013). https://doi.org/10.1007/978-88-7642-475-5_81 . http: //dx.doi.org/10.1007/978-88-7642-475-5_81

    work page doi:10.1007/978-88-7642-475-5_81 2013

  26. [26]

    Britz, T., Cameron, P.: Partially ordered sets. J. of Formalized Mathematics1 (2002)

    2002

  27. [27]

    Discrete Mathematics338(10), 1755–1762 (2015)

    Hell, P., Hernández-Cruz, C.: Point determining digraphs,{0, 1}-matrix par- titions, and dualities in full homomorphisms. Discrete Mathematics338(10), 1755–1762 (2015)

    2015

  28. [28]

    European Journal of Combinatorics31(1), 106–119 (2010) https://doi.org/10.1016/j.ejc

    Ball, R.N., Nešetřil, J., Pultr, A.: Dualities in full homomorphisms. European Journal of Combinatorics31(1), 106–119 (2010) https://doi.org/10.1016/j.ejc. 2009.04.004

    work page doi:10.1016/j.ejc 2010

  29. [29]

    Discrete Mathematics308(9), 1639–1652 (2008) https: //doi.org/10.1016/j.disc.2006.11.026

    Feder, T., Hell, P.: On realizations of point determining graphs, and obstructions to full homomorphisms. Discrete Mathematics308(9), 1639–1652 (2008) https: //doi.org/10.1016/j.disc.2006.11.026

    work page doi:10.1016/j.disc.2006.11.026 2008

  30. [30]

    Master’s thesis, Simon Fraser University (2006) 30

    Xie, W.: Obstructions to trigraph homomorphisms. Master’s thesis, Simon Fraser University (2006) 30

    2006

  31. [31]

    Combinatorica15(4), 475–480 (1995) https://doi.org/10.1007/ BF01192520

    Ahlswede, R., Erdős, P.L., Graham, N.: A splitting property of maxi- mal antichains. Combinatorica15(4), 475–480 (1995) https://doi.org/10.1007/ BF01192520

    1995

  32. [32]

    KAM-DIMATIA series835(2007)

    Ball, R.N., Nešetřil, J., Pultr, A.: Finite dualities, in particular in full homomor- phisms. KAM-DIMATIA series835(2007)

    2007

  33. [33]

    Discrete Mathematics5, 179–187 (1973)

    Sumner, D.P.: Point determination in graphs. Discrete Mathematics5, 179–187 (1973)

    1973

  34. [34]

    Discrete Applied Mathematics160(12), 1680–1690 (2012) https://doi.org/10.1016/j.dam.2012.03.029

    Bodirsky, M., Kára, J., Martin, B.: The complexity of surjective homomorphism problems—a survey. Discrete Applied Mathematics160(12), 1680–1690 (2012) https://doi.org/10.1016/j.dam.2012.03.029

    work page doi:10.1016/j.dam.2012.03.029 2012

  35. [35]

    Braunschweig: Friedr

    Reidemeister, K.: Einführung in die Kombinatorische Topologie. Braunschweig: Friedr. Vieweg&Sohn A.-G., Braunschweig (1932)

    1932

  36. [36]

    Cambridge University Press, Cambridge (1974)

    Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge (1974)

    1974

  37. [37]

    European J

    Malnič, A., Nedela, R., Škoviera, M.: Regular homomorphisms and regular maps. European J. Combin.23(4), 449–461 (2002)

    2002

  38. [38]

    Proceedings of the 12th ACM Symposium on Theory of Computing, 82–93 (1980)

    Angluin, D.: Local and global properties in networks of processors. Proceedings of the 12th ACM Symposium on Theory of Computing, 82–93 (1980)

    1980

  39. [39]

    Journal of Combinatorial Theory, Series B33(3), 231–238 (1982) https://doi.org/10.1016/0095-8956(82) 90042-9

    Leighton, F.T.: Finite common coverings of graphs. Journal of Combinatorial Theory, Series B33(3), 231–238 (1982) https://doi.org/10.1016/0095-8956(82) 90042-9

    work page doi:10.1016/0095-8956(82 1982

  40. [40]

    Computer Science Review2(2), 97–111 (2008) https://doi.org/10.1016/j.cosrev.2008.06.001

    Fiala, J., Kratochvíl, J.: Locally constrained graph homomorphisms — struc- ture, complexity, and applications. Computer Science Review2(2), 97–111 (2008) https://doi.org/10.1016/j.cosrev.2008.06.001

    work page doi:10.1016/j.cosrev.2008.06.001 2008

  41. [41]

    In: Jedrzejowicz, J., Szepietowski, A

    Fiala, J., Paulusma, D., Telle, J.A.: Matrix and graph orders derived from locally constrained graph homomorphisms. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS. Lecture Notes in Computer Science, vol. 3618, pp. 340–351. Springer, Berlin, Heidelberg (2005). https://doi.org/10.1007/11549345_30

    work page doi:10.1007/11549345_30 2005

  42. [42]

    Theoretical Computer Science17(1), 29–41 (1982) https://doi.org/10.1016/0304-3975(82)90129-3

    Welzl, E.: Color-families are dense. Theoretical Computer Science17(1), 29–41 (1982) https://doi.org/10.1016/0304-3975(82)90129-3

    work page doi:10.1016/0304-3975(82)90129-3 1982

  43. [43]

    European Journal of Combinatorics27(7), 1111–1116 (2006) https://doi.org/10.1016/j.ejc.2006.06.003

    Fiala,J.,Maxová,J.:Cantor-Bernsteintypetheoremforlocallyconstrainedgraph homomorphisms. European Journal of Combinatorics27(7), 1111–1116 (2006) https://doi.org/10.1016/j.ejc.2006.06.003

    work page doi:10.1016/j.ejc.2006.06.003 2006

  44. [44]

    In: Eades, P., Takaoka, T

    Fiala, J., Kratochvíl, J.: Complexity of partial covers of graphs. In: Eades, P., Takaoka, T. (eds.) ISAAC. Lecture Notes in Computer Science, vol. 2223, pp. 537–549. Springer, Berlin, Heidelberg (2001). https://doi.org/10.1007/ 3-540-45678-3_46

    2001

  45. [45]

    In: Lee, D.T., Teng, S.-H

    Kristiansen, P., Telle, J.A.: Generalizedh-coloring of graphs. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC. Lecture Notes in Computer Science, vol. 1969, pp. 456–466. Springer, Berlin, Heidelberg (2000). https://doi.org/10.1007/3-540-40996-3_39

    work page doi:10.1007/3-540-40996-3_39 1969

  46. [46]

    Journal of the American Mathe- matical Society3(4), 843–902 (1990)

    Bass, H., Kulkarni, R.: Uniform tree lattices. Journal of the American Mathe- matical Society3(4), 843–902 (1990)

    1990

  47. [47]

    Groups, Geometry, and Dynamics4, 863–872 (2011) 31

    Neumann, W.D.: On Leighton’s graph covering theorem. Groups, Geometry, and Dynamics4, 863–872 (2011) 31

    2011

  48. [48]

    Discrete Mathematics1(3), 257–268 (1971)

    Nešetřil, J.: Homomorphisms of derivative graphs. Discrete Mathematics1(3), 257–268 (1971)

    1971

  49. [49]

    Journal of Combinatorial Mathematics and Combinatorial Computing116, 169– 182 (2020)

    Naserasr, R., Sen, S., Sopena, É.: The homomorphism order of signed graphs. Journal of Combinatorial Mathematics and Combinatorial Computing116, 169– 182 (2020)

    2020

  50. [50]

    Order38, 257–269 (2021) https://doi.org/10.1007/s11083-020-09539-y 32

    Jakubíková-Studenovská, D.: Homomorphism order of connected monounary algebras. Order38, 257–269 (2021) https://doi.org/10.1007/s11083-020-09539-y 32

    work page doi:10.1007/s11083-020-09539-y 2021