Combinatorics · arXiv:2611.17047 v1 · submitted 12 Nov 2026 · 16 references
Integer Decomposition Property of Edge Polytopes of Weighted Oriented Graphs
The paper says
“We classify the lattice polytopes arising from vertex-weighted oriented graphs that have the integer decomposition property (IDP). Allowing vertex weights and edge orientations introduces non-vertex lattice points in the polytope which need to be accounted for when studying the IDP.”
more of the abstract
We can then identify forbidden induced subgraphs in the sense that their presence obstructs the IDP for the supergraph. We establish positive results for several families of graphs under suitable orientation and coprimality conditions, including weighted oriented paths and cycles, and show that any weighted oriented tree with a unique sink has the IDP.
from the abstract
Pith says
Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person
It can be wrong. Challenge this review or reply to it.
Holds up, with conditions. Solid IDP classification for weighted oriented graphs, but the converse of the balanced-cycle theorem is not proved. This line is wrong
4 major objections · 9 minor
How often objections from reviews like this one are right: not yet measured
Not checked: figures, code, what the 16 references say.
The paper says, at Theorem 5.11 (converse direction, proof paragraph)
The review did not quote this passage.
Pith says: Objection 1 of 4 · major
The converse (only if) direction of Theorem 5.11 is not proved. The proof states: 'Since Cn is balanced and uniformly weighted, then the number of clockwise and counterclockwise vertices are the same, and all non-sink, non-source vertices cannot be all counter-clockwise or all clockwise, therefore Cn has the structure of Proposition 4.2.'
more of objection 1
This is an assertion without derivation. Proposition 4.2 describes a specific odd-length path-like structure (2r+1 vertices) with a particular alternating pattern. A balanced uniformly weighted cycle with mixed vertices could have a different pattern (e.g., a 6-cycle with alternating sinks, sources, and mixed vertices) that satisfies the balance condition but does not contain the induced subgraph of Proposition 4.2. The paper provides no argument that the presence of a non-sink, non-source vertex forces the existence of that specific induced subgraph. Without this, the converse is unsupported. This is a load-bearing gap because the 'if and only if' claim is a central result.
The paper says, at Theorem 4.5, even n case
The review did not quote this passage.
Pith says: Objection 2 of 4 · major
The proof of Theorem 4.5 for even n is incomplete. The text says: 'The proof is similar to the odd case, and the details are left to the reader.' Given that the odd case already involves nontrivial sign analysis and the even case has a different sign pattern (det(C_n) negative), leaving the verification to the reader is insufficient for a rigorous proof.
more of objection 2
The claim that the even case follows similarly is not justified, especially because the sign of the determinant changes the direction of inequalities. This gap affects the classification of forbidden structures for even cycles, which is used in the overall characterization.
The paper says, at Proposition 3.10, characterization of non-vertex lattice points for naturally oriented cycles
The review did not quote this passage.
Pith says: Objection 3 of 4 · major
Proposition 3.10 claims that for a naturally oriented cycle with uniform weight w≥2, the non-vertex lattice points are exactly the set L = {λ∈N_0^n | λ_i ≥ 1, |λ| = w+1}. The proof uses the inverse matrix C_n^{-1} and argues that a = C_n^{-1} λ has nonnegative entries and sum 1.
more of objection 3
However, the argument that a_i ≥ 0 for all i relies on bounding inequalities that assume n≥3 and w≥2, but the derivation of the bounds (e.g., λ_i ≤ w+2-n) is not fully justified. Moreover, the proof that every λ in L is indeed a lattice point of P_{C_n} requires showing that a_i ≥ 0, but the inequalities given are not rigorous for all possible λ. For example, the bound λ_i ≤ w+2-n is derived from |λ|=w+1 and λ_i ≥ 1, but this is only valid if n≥3; for n=3, w+2-n = w-1, which is fine, but the argument that a_1 ≥ 0 uses a sum that may not be nonnegative for all choices of λ. The proof appears to assume a particular ordering of λ_i that may not hold. This proposition is used in Theorem 4.5, so its correctness is important.
The paper says, at Proposition 5.3, proof using row reduction and subsystems
The review did not quote this passage.
Pith says: Objection 4 of 4 · major
The proof of Proposition 5.3 reduces the system to independent subsystems (6) and claims that nonnegative integer solutions exist based on the values T_l. The construction of solutions when T_l = k_l w + t_l with 0 < t_l < w sets d_{l,t}=1 and others 0.
more of objection 4
However, it is not verified that the resulting d_{l,t} are integers between 0 and w-1 (they are 0 or 1, which is fine) and that the corresponding c_{2l-1}, c_{2l} are nonnegative integers. The argument that a_{2l} - k_l - 1 ≥ 0 is not explicitly justified; it relies on the inequality a_{2l} ≥ k_l + 1, which follows from T_l < w a_{2l}? The proof states 'If instead T_l = k_l w + t_l with 0 ≤ k_l < a_{2l} and 1 ≤ t_l < w', but it is not shown that k_l < a_{2l} always holds. This needs clarification.
9 minor objections
The paper says, at General
Pith says: minor objection 1 of 9
The paper uses the term 'normal' interchangeably with IDP, but Remark 2.9 notes that some authors distinguish them. It would be helpful to state explicitly which definition is adopted (IDP as defined in Definition 2.8(b)).
The paper says, at Lemma 2.6
Pith says: minor objection 2 of 9
The determinant formula det(C_n) = 1 + (-1)^{n-1} w^n is given without proof. While it is straightforward, a brief derivation or reference would improve readability.
show 7 more
The paper says, at Proposition 3.2
Pith says: minor objection 3 of 9
The statement says 'with weight w_1 on vertex x_1 and w_3 on vertex x_3'. It might be clearer to explicitly state that the path is x_2 → x_1 and x_2 → x_3, with vertex x_2 having weight 1 (or unspecified). The weights on x_2 are not mentioned; presumably they are 1 (since it is a source with out-edges). This should be clarified.
The paper says, at Example 4.4
Pith says: minor objection 4 of 9
The example compares H and H' with different orientations and claims that H' has IDP based on Macaulay2 computation. It would be helpful to state whether this is a general phenomenon or just an example.
The paper says, at Proposition 4.6
Pith says: minor objection 5 of 9
The statement assumes 'P_H has no non-vertex lattice points' but the proof does not explicitly verify this condition; it relies on the structure and coprimality conditions. The condition should be stated as part of the hypothesis or justified.
The paper says, at Theorem 5.9
Pith says: minor objection 6 of 9
The proof is very brief: it argues that because G has a unique sink, there are no non-vertex lattice points, and then uses a leaf elimination argument to show that any a in A[P_G] must have c_i = 0. However, the step 'we can pick another leaf of G \ {e_1} and continue this process to conclude that c_i = 0 for all i' is not fully explained.
more of objection 6
It assumes that after removing a leaf, the remaining graph still has a unique sink? This needs more justification.
The paper says, at Proposition 5.12
Pith says: minor objection 7 of 9
The proof uses Lemma 5.5 which requires pairwise coprime weights. The statement says 'all the weights of the sink vertices are pairwise coprime'. It should be clarified whether the source vertices also have weights that are coprime to each other or not; the proof only uses coprimality of sink weights (odd-indexed vertices).
The paper says, at Notation
Pith says: minor objection 8 of 9
The paper uses both N and N_0; it would be helpful to define them explicitly at the start.
The paper says, at References
Pith says: minor objection 9 of 9
Reference [6] is Hà and Lin, 'Normal 0-1 polytopes', which is published. The paper cites it for Proposition 2.12 and Theorem 4.1. This is appropriate.
What would settle it
Construct a balanced uniformly weighted 6-cycle with vertices: x1 (sink), x2 (source), x3 (mixed, weight w), x4 (sink), x5 (source), x6 (mixed, weight w), edges oriented accordingly. Check whether the balance condition (Definition 5.10(b)) holds. If it does, compute the edge polytope and test IDP via Macaulay2 or by checking whether the point a = (1,1,1,1,1,1) (if w=2) lies in 2P but cannot be expressed as a sum of two lattice points. If such a cycle has IDP, the converse of Theorem 5.11 is false. If it does not have IDP, the authors must provide a general proof that any balanced uniformly weighted cycle with a non-sink, non-source vertex contains the Proposition 4.2 structure.
from the skeptic's reading
How the review went
4 readings by deepseek-v4-flash · 13 Nov 2026
- Reader holds up, with conditions
- Skeptic agrees
- Editor wrote the verdict above
- Referee major revision: 4 major objections, 9 minor
Not run on this paper: the simulated authors' defence.
Pith did not check this review's objections against the paper.
The review in full
The review in brief, machine-written
This paper extends the IDP (integer decomposition property) literature from 0-1 polytopes and unweighted edge polytopes to vertex-weighted oriented graphs. The main contributions are: (1) a description of non-vertex lattice points in these polytopes (Section 3), (2) a catalogue of forbidden induced subgraphs (Section 4), and (3) positive IDP results for weighted oriented paths, unique-sink trees, and balanced uniformly weighted cycles (Section 5). The positive theorems for paths and unique-sink trees are proved in detail and appear correct. The paper is clearly written and the examples are helpful.
The soft spot is Theorem 5.11, the balanced-cycle classification. The 'if' direction (all vertices sinks or sources implies IDP) is argued via a reduction to the path case and a linear algebra argument that looks plausible. The 'only if' direction, however, is not proved. The proof states: 'Since Cn is balanced and uniformly weighted, then the number of clockwise and counterclockwise vertices are the same, and all non-sink, non-source vertices cannot be all counter-clockwise or all clockwise, therefore Cn has the structure of Proposition 4.2.' This is an assertion, not a derivation. Proposition 4.2 describes a specific odd-length path-like structure. A balanced uniformly weighted 6-cycle with alternating sinks, sources, and mixed vertices satisfies the balance condition but does not contain the induced subgraph of Proposition 4.2. The paper provides no argument that a non-sink, non-source vertex forces that specific induced subgraph. Without this, the converse is unsupported. The authors should either supply a proof or downgrade the claim to a conjecture.
Minor issues: Theorem 4.5 (naturally oriented cycles) leaves the even-n verification to the reader, which is acceptable for a journal but should be checked. The abstract says 'classify' but the classification is partial (paths, cycles, unique-sink trees). That is fine for a paper, but the abstract overstates slightly.
Who this is for: researchers in algebraic combinatorics, Ehrhart theory, and toric geometry. The paper is a solid step within its subfield, not a breakthrough. It deserves a serious referee: the positive results are new and the gap in Theorem 5.11 is fixable. I would accept peer review and recommend the editor send it out, with the expectation that the authors address the converse of Theorem 5.11.
The strongest objection
The 'only if' direction of Theorem 5.11 asserts that if a balanced uniformly weighted cycle has the IDP then all vertices are sinks or sources. The proof states: 'Since Cn is balanced and uniformly weighted, then the number of clockwise and counterclockwise vertices are the same, and all non-sink, non-source vertices cannot be all counter-clockwise or all clockwise, therefore Cn has the structure of Proposition 4.2.' This is not a derivation; it is an assertion. Proposition 4.2 describes a specific odd-length path-like structure (2r+1 vertices) with a particular alternating pattern of sinks and sources. A balanced uniformly weighted cycle with mixed vertices could have a different pattern (e.g., a 6-cycle with alternating sinks, sources, and mixed vertices) that satisfies the balance condition but does not contain the induced subgraph of Proposition 4.2. The paper provides no argument that the presence of a non-sink, non-source vertex forces the existence of that specific induced subgraph. Without this, the converse is unsupported.
The reader's weakest_assumption correctly identifies the unproven structural claim in the converse of Theorem 5.11. The paper's own sentence [b297] states the theorem, and the proof paragraph (starting 'We now prove the converse...') contains the unsupported assertion. The reader's concern is precise: a uniformly weighted 6-cycle with alternating sinks, sources, and mixed vertices can satisfy the balance equation without containing the odd-length Prop 4.2 shape as an induced subgraph. My analysis confirms this gap. The paper acknowledges no limitation here; the proof simply declares the structure without justification. This is the single most load-bearing concern because the 'if and only if' classification of cycles is a headline result, and the 'only if' direction is essential to the claim of classification. If this direction fails, the paper's strongest claim is weakened from a classification to a sufficient condition. The concrete test I propose would either falsify the converse or force the authors to provide the missing argument. I agree with the reader's assessment, and the verdict should remain CONDITIONAL because the gap is real but potentially fixable with additional reasoning. I do not recommend REJECT because the positive results (paths, unique-sink trees) are independent and valuable, and the 'if' direction of Theorem 5.11 is correctly proved. The paper's self-citations are appropriate and not circular. No ad hominem or theatrical language is used.
The referee's report
If correct, the results provide a near-classification of IDP for edge polytopes of weighted oriented graphs within the studied families. The identification of forbidden induced subgraphs and the positive results for trees and cycles are nontrivial extensions of prior work on 0-1 polytopes. The paper is clearly written and the proofs are largely detailed. The main significance lies in connecting combinatorial graph structure (sink/source patterns, coprimality) to the IDP, which is a central property in Ehrhart theory and toric geometry.
Pith's reading of the paper (a machine's summary, not the authors')
The paper studies edge polytopes associated to vertex-weighted oriented graphs and asks when these polytopes have the integer decomposition property (IDP)—meaning every lattice point in any dilation can be expressed as a sum of lattice points from the original polytope. The authors identify forbidden induced subgraphs whose presence destroys the IDP, and they prove positive results for several families: weighted oriented paths and cycles whose vertices are all sinks or sources (with either uniform weights or coprime sink weights), and any weighted oriented tree with a unique sink. The central claim is that for a balanced uniformly weighted cycle, the IDP holds if and only if every vertex is a sink or source.
What carries the argument. The central object is the edge polytope P_G of a weighted oriented graph G, defined as the convex hull of the columns of its incidence matrix. The key machinery includes the characterization of non-vertex lattice points in P_G (Proposition 3.1, Lemma 3.5, Proposition 3.10), the identification of forbidden induced subgraphs that prevent IDP (Proposition 4.2, Theorem 4.5, Proposition 4.6), and the use of row reduction and combinatorial arguments to show that certain families (paths, cycles, trees with a unique sink) satisfy IDP.
Core claim. The paper establishes that for edge polytopes of vertex-weighted oriented graphs, the integer decomposition property (IDP) is characterized by the absence of certain induced subgraphs and, in the case of uniformly weighted balanced cycles, by the condition that every vertex is either a sink or source. It provides positive results for paths and cycles under sink/source orientations and coprimality or uniform weight conditions, and proves that any weighted oriented tree with a unique sink has the IDP.
The premise it rests on. The proof that a balanced uniformly weighted cycle with a non-sink, non-source vertex must contain the specific induced subgraph of Proposition 4.2 is stated without derivation, and this structural claim is not forced by the balance condition alone.
If the paper is right (Pith's inferences, not the authors')
If correct, these results provide a near-complete classification of when edge polytopes of weighted oriented graphs have the IDP, extending previous work on 0-1 polytopes and unweighted graphs.
The forbidden subgraph characterization can be used to test whether a given weighted oriented graph yields an IDP polytope by checking for the presence of the described induced subgraphs.
The positive results for trees with a unique sink and for paths/cycles with sink/source orientations give explicit families of IDP polytopes, which may be useful in Ehrhart theory and integer programming.
The coprimality conditions (Proposition 5.7, Proposition 5.12) show that IDP can hold even when non-vertex lattice points are absent, relying only on number-theoretic properties of the weights.
The balanced-cycle classification (Theorem 5.11) gives a necessary and sufficient condition for IDP in a natural family, showing that the presence of any vertex that is neither sink nor source destroys IDP.
The 'only if' direction of Theorem 5.11 depends on the assertion that a balanced uniformly weighted cycle with a non-sink, non-source vertex must contain the induced subgraph of Proposition 4.2. This structural claim is not fully justified in the paper; if it fails, the classification would be incomplete.
The results suggest that the IDP property for edge polytopes of weighted oriented graphs is tightly controlled by the orientation pattern (sink/source structure) and the coprimality of weights, rather than by the overall graph topology. One could test this by constructing a cycle with mixed orientations that is not balanced but still has IDP.
The paper's approach of characterizing non-vertex lattice points and then using them to prove IDP (or its failure) could be extended to other families of polytopes arising from monomial maps, such as those from hypergraphs or directed graphs with multiple edge types.
The explicit construction of a point in A[P_H]\K[P_H] in Proposition 4.2 provides a concrete witness for the failure of IDP, which could be used to algorithmically check IDP for small graphs.
Check this review
Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.
How often reviews like this one are right
Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.
How often objections from reviews like this one are right: not yet measured
Reviews by people
This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.
The paper
Abstract
We classify the lattice polytopes arising from vertex-weighted oriented graphs that have the integer decomposition property (IDP). Allowing vertex weights and edge orientations introduces non-vertex lattice points in the polytope which need to be accounted for when studying the IDP. We can then identify forbidden induced subgraphs in the sense that their presence obstructs the IDP for the supergraph. We establish positive results for several families of graphs under suitable orientation and coprimality conditions, including weighted oriented paths and cycles, and show that any weighted oriented tree with a unique sink has the IDP.
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.
abstract compiled · 2026-11-13
The authors' main claim, as the classifier picked it out 0.72
“We classify the lattice polytopes arising from vertex-weighted oriented graphs that have the integer decomposition property (IDP).”
How the main claim is stated: asserted 1.00
What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.50 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.07 · compares with prior results 0.09 · mentions code or data availability 0.01
The abstract, sentence by sentence
This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| We classify the lattice polytopes arising from vertex-weighted oriented graphs that have the integer decomposition property (IDP). | contribution 0.97 | 0.95 | 0.60 | asserted 1.00 |
| Allowing vertex weights and edge orientations introduces non-vertex lattice points in the polytope which need to be accounted for when studying the IDP. | background 0.93 | 0.24 | 0.04 | asserted 0.96 |
| We can then identify forbidden induced subgraphs in the sense that their presence obstructs the IDP for the supergraph. | result 0.77 | 0.88 | 0.16 | asserted 0.89 |
| We establish positive results for several families of graphs under suitable orientation and coprimality conditions, including weighted oriented paths and cycles, and show that any weighted oriented tree with a unique sink has the IDP. | result 0.98 | 0.95 | 0.49 | asserted 1.00 |
What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00
What was examined, and what was not
Sources read
- arXiv listing abstract v1
Not examined
- full text
- figures and tables
- references and citing sentences
- relations to other papers
Levels run
- P abstract
Not run
- S sections
- T body sentences
- C citations
- R cross-paper relations
How the labels were made
Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-13: 1 request, 3,615 input tokens.
Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON
References (16)
- [1] M. Beck, C. Haase, A. Higashitani, J. Hofscheier, K. Jochemko, L. Katth¨ an, and M. Micha l ek,Smooth centrally symmetric polytopes in dimension 3 are IDP, Ann. Comb.23(2019), no. 2, 255–262 on Pith
- [2] J. Biermann, S. Kara, K. N. Lin, and A. O’Keefe,Algebraic invariants of weighted oriented graphs, J. Algebraic Combin.55(2022), no. 2, 461–491 on Pith
- [3] W. Bruns and J. Gubeladze,Polytopes, rings, andK-theory, Springer Monographs in Mathematics, Springer, Dordrecht, 2009 on Pith
- [4] P. Gimenez, J. Mart ´ ınez-Bernal, A. Simis, R. Villarreal, and C. Vivares,Symbolic powers of monomial ideals and Cohen-Macaulay vertex-weighted digraphs, Singularities, algebraic geometry, commutative algebra, and related topics, 2018, pp. 491–510 on Pith
- [5] D. R. Grayson and M. E. Stillman,Macaulay2, a software system for research in algebraic geometry on Pith
- [6] H. T. H` a and K. Lin,Normal 0-1 polytopes, SIAM Journal on Discrete Mathematics1(2015), no. 1, 210–223 on Pith
- [7] H. T. H` a, K. Lin, S. Morey, E. Reyes, and R. Villarreal,Edge ideals of oriented graphs, Internat. J. Algebra and Comput.29(2019), no. 03, 535–559 on Pith
- [8] A. Higashitani,Minkowski sum of polytopes and its normality, J. Math. Soc. Japan68(2016), no. 3, 1147–1159 on Pith
- [9] J. Mart ´ ınez-Bernal, Y. Pitones, and R. Villarreal,Minimum distance functions of graded ideals and reed–Muller-type codes, J. Pure Appl. Algebra221(2017), no. 2, 251–275 on Pith
- [10] E. Miller and B. Sturmfels,Combinatorial commutative algebra, Graduate Texts in Mathematics, vol. 227, Springer-Verlag, New York, 2005 on Pith
- [11] H. Ohsugi and T. Hibi,Toric ideals generated by quadratic binomials, J. Algebra218(1999), no. 2, 509–527 on Pith
- [12] H. Ohsugi and T. Hibi,Normal polytopes arising from finite graphs, J. Algebra207(1998), no. 2, 409–426 on Pith
- [13] Y. Pitones, E. Reyes, and J. Toledo,Monomial ideals of weighted oriented graphs, Electron. J. Combin. 26(2019), no. 3, Paper No. 3.44, 18 on Pith
- [14] A. Schrijver,Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathe- matics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication on Pith
- [15] B. Sturmfels,Gr¨ obner bases and convex polytopes, University Lecture Series, vol. 8, American Math- ematical Society, Providence, RI, 1996 on Pith
- [16] R. Villarreal,Rees algebras of edge ideals, Comm. Algebra23(1995), no. 9, 3513–3524. Department of Mathematics and Computer Science, Hobart and William Smith Col- leges, 300 Pulteney St. Geneva, NY 14456, USA Email address:biermann@hws.edu Department of Mathematics, Penn State... on Pith
Challenges and discussion
Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment