pith. sign in

arxiv: 2606.26689 · v1 · pith:KNFRJ5XJnew · submitted 2026-06-25 · 🧮 math.AC · math.CO

An algebraic study of ideals of weak graph homomorphisms

Francesco Navarra , Ayesha Asloob Qureshi , Seyed Amin Seyed Fakhari This is my paper

Pith reviewed 2026-06-26 02:04 UTC · model grok-4.3

classification 🧮 math.AC math.CO
keywords weak graph homomorphismsmonomial idealslinear resolutionsCohen-Macaulay ringsprojective dimensionCastelnuovo-Mumford regularityunmixed idealsgraph theory
0
0 comments X

The pith

The ideal I_{G→H} of weak graph homomorphisms has powers with linear resolutions exactly when G and H satisfy a specific combinatorial characterization.

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

The paper defines the monomial ideal I_{G→H} whose generators encode the weak homomorphisms from a finite simple graph G to another such graph H, with both graphs undirected or both directed. It then gives a complete list of the pairs G and H for which some power of this ideal has a linear resolution, and proves the property holds for one power if and only if it holds for every power. This allows direct determination of the Castelnuovo-Mumford regularity and projective dimension from the graphs alone. The work additionally determines when the ideals are unmixed or Cohen-Macaulay. These results tie the existence of graph homomorphisms to the algebraic resolution behavior of associated ideals.

Core claim

We introduce the ideal I_{G→H} of weak graph homomorphisms for finite simple graphs G and H that are both undirected or both directed. We characterize all such pairs G and H for which every power of I_{G→H} has a linear resolution. We further investigate the unmixedness, Cohen-Macaulayness, projective dimension, and Castelnuovo-Mumford regularity of these ideals.

What carries the argument

The monomial ideal I_{G→H} generated by the monomials corresponding to weak homomorphisms from G to H.

If this is right

  • The linear resolution property for powers of I_{G→H} is completely decided by the structure of the input graphs G and H.
  • For the characterized pairs the projective dimension and Castelnuovo-Mumford regularity of I_{G→H} become explicitly computable from the graphs.
  • Unmixedness and the Cohen-Macaulay property of I_{G→H} hold or fail according to the same graph conditions that govern the resolution property.

Where Pith is reading between the lines

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

  • The same characterization technique could be applied to ideals arising from other homomorphism notions such as induced or list homomorphisms.
  • The equivalence between some and all powers having linear resolutions may extend to related monomial ideals attached to directed graphs with multiple edge types.
  • Graph algorithms that enumerate homomorphisms could now be repurposed to test the algebraic resolution properties of I_{G→H} without computing minimal free resolutions.

Load-bearing premise

The graphs G and H are finite simple graphs that are either both undirected or both directed.

What would settle it

A pair of graphs G and H such that some but not all powers of I_{G→H} have a linear resolution, or a pair outside the characterized class whose powers nevertheless admit linear resolutions.

Figures

Figures reproduced from arXiv: 2606.26689 by Ayesha Asloob Qureshi, Francesco Navarra, Seyed Amin Seyed Fakhari.

Figure 1
Figure 1. Figure 1: G2 and G3 comes from G1 by shrinking the 3-cycle and the 4-cycle, respectively. As Example 3.12 shows even if G is a simple graph, the graph G′ obtained by shrinking a directed cycle of G is not necessarily simple. Indeed, for some vertex i ∈ [n] \ V (C), both edges (0, i) and (i, 0) may appear in G′ . However, the definition of IG→H makes sense when the underlying graph of G has parallel edges. Moreover, … view at source ↗
read the original abstract

Let $G$ and $H$ be finite simple graphs and assume that either both are undirected or both are directed. We introduce and study the ideal of weak graph homomorphisms $I_{G\to H}$. We characterize all graphs $G$ and $H$ for which every (equivalently, some) power of $I_{G\to H}$ has a linear resolution. Moreover, unmixedness, Cohen-Macaulayness, projective dimension and Castelnuovo-Mumford regularity of these ideals are studied.

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 / 2 minor

Summary. The manuscript introduces the ideal I_{G→H} of weak graph homomorphisms between finite simple graphs G and H (both undirected or both directed). It characterizes all such pairs (G,H) for which every power (equivalently, some power) of I_{G→H} has a linear resolution, and studies unmixedness, Cohen-Macaulayness, projective dimension, and Castelnuovo-Mumford regularity of these ideals.

Significance. If the characterizations are correct, the work supplies a new family of monomial ideals arising from graph homomorphisms and determines precisely when they satisfy strong homological properties such as linear resolutions of powers. Explicit combinatorial conditions on G and H that control algebraic invariants like pd and regularity would be a useful addition to the literature on combinatorial commutative algebra.

minor comments (2)
  1. The abstract claims an equivalence between 'every power' and 'some power' having linear resolution; the manuscript should state explicitly in which section this equivalence is proved and whether it relies on any additional hypotheses on G or H.
  2. Notation for the ideal I_{G→H} and the weak homomorphism condition should be recalled or cross-referenced at the beginning of the main results section for readers who may not be familiar with the graph-theoretic definition.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment of the significance of the work, and recommendation for minor revision. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No circularity: new ideal defined from first principles; characterizations derived directly from graph and ideal properties

full rationale

The paper introduces the ideal I_{G→H} as a new object for finite simple graphs G and H (matching directed/undirected type). All subsequent results—characterizations of graphs where powers have linear resolution, plus unmixedness, Cohen-Macaulayness, pd, and regularity—are obtained by direct algebraic and combinatorial arguments from this definition and standard commutative algebra tools. No fitted parameters, self-referential equations, or load-bearing self-citations appear in the abstract or claim structure. The derivation chain is self-contained against external benchmarks and does not reduce any prediction or uniqueness claim to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Ledger constructed from abstract only. The central claim rests on the definition of the new ideal and standard assumptions about graphs; no fitted parameters or invented entities with external evidence are visible.

axioms (1)
  • domain assumption G and H are finite simple graphs, either both undirected or both directed.
    Explicitly stated as the setting for the definition of I_{G→H}.
invented entities (1)
  • Ideal of weak graph homomorphisms I_{G→H} no independent evidence
    purpose: Algebraic object encoding weak homomorphisms between graphs G and H.
    Newly defined in the paper; no independent evidence outside the definition is provided in the abstract.

pith-pipeline@v0.9.1-grok · 5617 in / 1395 out tokens · 21020 ms · 2026-06-26T02:04:20.988729+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

22 extracted references · 1 canonical work pages

  1. [1]

    D’Al ´ ı, G

    A. D’Al ´ ı, G. Fløystad, A. Nematbakhsh, Resolutions of letterplace ideals of posets, J. Algebr. Comb. 45 (2016), 911-930

    2016

  2. [2]

    D’Al ´ ı, G

    A. D’Al ´ ı, G. Fløystad, A. Nematbakhsh, Resolutions of co-letterplace ideals and generalizations of Bier spheres, Trans. Amer. Math. Soc. 371 (2019), 8733–8753

    2019

  3. [3]

    Beyarslan, H

    S. Beyarslan, H. T. H` a, T. N. Trung, Regularity of powers of fo rests and cycles. J. Algebr. Comb. 42 (2015), 1077–1095

    2015

  4. [4]

    Bigdeli, J

    M. Bigdeli, J. Herzog, R. Zaare-Nahandi, On the index of powers o f edge ideals, Comm. Algebra 46 (2018), 1080–1095

    2018

  5. [5]

    H. J. Chiang-Hsieh, Some arithmetic properties of matroidal idea ls, Comm. Algebra 38 (2010) 944–952

    2010

  6. [6]

    V. Ene, J. Herzog, F. Mohammadi, Monomial ideals and toric rings o f Hibi type arising from a finite poset, Eur. J. Comb. 32 (2011), 404–421

    2011

  7. [7]

    Fløystad, B

    G. Fløystad, B. M. Greve, J. Herzog, Letterplace and co-lette rplace ideals of posets, J. Pure Appl. Algebra 221 (2017), 1218–1241

    2017

  8. [8]

    Gasharov, I

    V. Gasharov, I. Peeva, V. Welker, The LCM-lattice in monomial re solutions, Math. Res. Lett. 6 (1999), 521–532

    1999

  9. [9]

    Macaulay2: a software system fo r research in algebraic geometry

    D. R. Grayson, M. E. Stillman, “Macaulay2: a software system fo r research in algebraic geometry”, available at http://www.math.uiuc.edu/Macaulay2

  10. [10]

    H. T. H` a, H. D. Nguyen, N. V. Trung, T. N. Trung, Symbolic pow ers of sums of ideals, Math. Z. 294 (2020), 1499–1520

    2020

  11. [11]

    Herzog, A generalization of the Taylor complex construction , Comm

    J. Herzog, A generalization of the Taylor complex construction , Comm. Algebra 35 (2007), 1747–1756

    2007

  12. [12]

    Herzog, T

    J. Herzog, T. Hibi, Distributive lattices, bipartite graphs and Ale xander duality, J. Algebraic Combin. 22 (2005), 289–302

    2005

  13. [13]

    Herzog, T

    J. Herzog, T. Hibi, Monomial Ideals, Springer London, 2010

    2010

  14. [14]

    Herzog, T

    J. Herzog, T. Hibi, X. Zheng, Dirac’s theorem on chordal graph s and Alexander duality, Eur. J. Comb. 25 (2004), 949–960

    2004

  15. [15]

    Herzog, A

    J. Herzog, A. Qureshi, A. Shikama, Alexander duality for monom ial ideals associated with isotone maps between posets, J. Algebra Appl. 15 (2016), 1650089

    2016

  16. [16]

    L. T. Hoa, N. D. Tam, On some invariants of a mixed product of ide als, Arch. Math 94 (2010), 327–337

    2010

  17. [17]

    Juhnke-Kubitzke, L

    M. Juhnke-Kubitzke, L. Katth¨ an, S. Saeedi Madani, Algebra ic properties of ideals of poset homomorphisms, J. Algebraic Combin. 44 (2016), 757–784

    2016

  18. [18]

    Knauer, Algebraic Graph Theory: Morphisms, Monoids and Ma trices, Walter de Gruyter, Berlin (2011)

    U. Knauer, Algebraic Graph Theory: Morphisms, Monoids and Ma trices, Walter de Gruyter, Berlin (2011)

    2011

  19. [19]

    D. Lu, Z. Wang, The resolutions of generalized co-letterplace id eals and their powers, J. Algebra 673 (2025), 321–350

    2025

  20. [20]

    Navarra, graph-homomorphism-ideals (Version 1.0.0) [Computer software]

    F. Navarra, graph-homomorphism-ideals (Version 1.0.0) [Computer software]. (2026) https://doi.org/10.5281/zenodo.20044872

    work page doi:10.5281/zenodo.20044872 2026

  21. [21]

    Rauf, Depth and Stanley depth of multigraded modules, Comm

    A. Rauf, Depth and Stanley depth of multigraded modules, Comm. Algebra 38 (2010), 773–784

    2010

  22. [22]

    R. H. Villarreal, Monomial algebras , Second edition, Monograph and Research notes in Mathematics, C RC press, 2015. (Francesco Navarra) Sabanci University, F aculty of Engineering and Natural Sci ences, Orta Ma- halle, Tuzla 34956, Istanbul, Turkey Email address : francesco.navarra@sabanciuniv.edu (Ayesha Asloob Qureshi) Sabanci University, F aculty of E...

    2015