REVIEW 2 major objections 4 minor 1 cited by
The graph of implicit edge dependencies for indecomposability and beyond
T0 review · 2 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read A single graph of forced edge-length equalities now certifies indecomposability of polytopes, unifying the classical tests and yielding new indecomposable deformed permutahedra.
desk verdict Strong new framework for indecomposability, with a real but local counting error that should be fixed before the paper's advertised bounds are trusted. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the graph of implicit edge dependencies, whose nodes are the non-degenerate edges of a framework and whose arcs record pairs of edges whose length ratios are forced to stay equal across all deformations. Dependency is transitive, so connected components are cliques, and indecomposability is equivalent to this graph being connected. The proof machinery has three parts: adding implicit edges (vertex pairs whose difference scales by a common factor in every deformation) does not change the deformation cone; projecting a framework along a subspace and contracting degenerate edges lifts dependencies from the projected framework back to the original; and a covering family of
What would settle it
Solve the linear cycle equations for the deformation cone of the 4-dimensional polytope Zbar_{2,3}: if the solution space has dimension greater than one, the claimed indecomposability is false; if exactly one, the main application is confirmed. A cheaper local test is to build the graph of edges parallel to a fixed direction a_1 b_1 in Zbar_{2,3}, delete the nodes corresponding to the two truncated vertices, and check whether the remaining graph is connected—the theorem's proof requires it.
Extended reading notes
Core claim
The central claim is that indecomposability of a polytope or framework can be read off from a graph of forced edge-length equalities. Two edges are dependent if the ratio of their lengths is the same in every deformation; a framework is indecomposable exactly when all non-degenerate edges are pairwise dependent, i.e. when this graph is complete. The paper's main theorem states a sufficient condition: if some subset S of vertices is dependent (all pairs joined by paths of dependent implicit edges) and a covering family of flats—each flat being a connected subconfiguration, with facets as a special case—has every member containing a vertex of S, then the whole framework is indecomposable. This
Load-bearing premise
The proof of indecomposability for the new examples rests on identifying the graph of edges parallel to a fixed direction in a truncated graphical zonotope with the 1-skeleton of the contracted graphical zonotope, and on that graph remaining connected after the one or two truncated vertices are deleted; if this identification or the post-deletion connectivity fails, the central application collapses.
Editorial extensions
If this is right
- For every N at least 4, there are at least 2^floor((N-1)/2) non-isomorphic indecomposable deformed N-permutahedra that are not matroid polytopes, providing new rays of the submodular cone.
- The 1987 conjecture asserting that indecomposable polytopes must have relatively few vertices compared with their number of facets is false in dimension 4, with explicit 4-dimensional examples satisfying the conjecture's numerical condition yet still indecomposable.
- The dimension of a deformation cone is bounded above by the number of connected components of the edge-dependency graph, and the deformation cone of a Cartesian product is the product of the factor deformation cones.
- Taking permutahedral wedges of these indecomposable examples yields at least (N-1)!/3! non-normally-equivalent indecomposable deformed N-permutahedra that are not matroid polytopes.
- Stacking vertices on facets of parallelogramic Minkowski sums of indecomposable polytopes gives indecomposable polytopes exactly when a certain graph recording which summands appear together in the stacked facets is connected.
Reading between the lines
- The covering-flat formulation suggests indecomposability is a local-to-global phenomenon: one only needs a dependent core touching enough faces, so similar criteria may transfer to polytopes obtained by face subdivisions or perturbations that preserve the edge-dependency graph.
- The projection-and-lift mechanism gives a general recipe for other polytope families: find a direction in which a projection is indecomposable and lift that dependency back; this could generate new indecomposable families from zonotopes beyond the complete-bipartite case.
- The refutation in dimension 4 leaves open whether higher-dimensional analogues of the old vertex/facet conjecture exist; the edge-dependency graph may be a more practical sufficient condition than numerical inequalities for building such counterexamples.
- The deformation-cone dimension bounds could serve as a fast combinatorial heuristic—count connected components of the edge-dependency graph—to screen candidates for extreme rays of the submodular cone before running full linear-programming checks.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a graph of (implicit) edge dependencies for frameworks and uses it to give new indecomposability criteria for frameworks and polytopes. The central result, Theorem 2.6.4, states that a framework is indecomposable if it has a dependent vertex set S and a covering family of flats each containing a vertex of S. The authors show that this criterion subsumes and generalizes earlier criteria of Shephard, Kallay, McMullen, and others. The main application is to graphical zonotopes of complete bipartite graphs: after one or two deep truncations, the resulting polytopes are claimed to be indecomposable deformed permutahedra that are not matroid polytopes. Further applications include new lower bounds on the number of rays of the submodular cone, a negative answer to Smilansky's 1987 conjecture in dimension 4, bounds on deformation cones, and constructions of uniquely decomposable polytopes.
Significance. If the central results are correct, the paper offers a genuinely useful framework: the cycle-equation formulation is self-contained, Theorem 2.6.4 is proved directly from the deformation equations, and the method recovers several classical criteria in a uniform language. The construction of indecomposable deformed permutahedra that are not matroid polytopes is a substantive contribution to the long-standing problem of understanding extreme rays of the submodular cone. The paper also contains several interesting auxiliary results, such as the product formula for deformation cones and the treatment of parallelogramic Minkowski sums. However, the advertised quantitative lower bound in Corollary 3.3.5 is not supported by the provided proof, and one load-bearing lemma in the main application is stated with only a sketch. These issues do not necessarily invalidate the core framework, but they must be addressed before the paper can be accepted.
major comments (2)
- [§3.3, Corollary 3.3.5 and its proof] The counting argument for the lower bound is not sound. First, for each n in the stated range there are two polytopes, Zbar_{n,m} and Ztilde_{n,m}, so the construction gives at most 2 floor((N-1)/2) examples, not 2^{floor((N-1)/2)}. More seriously, the facet-count formula quoted in the proof is contradicted by the paper's own Example 3.3.1: for N=4, n=1 the formula gives 2^4 + 4 + 2 - (2 + 8) = 12 facets, while Example 3.3.1 reports that Zbar_{1,3} (strawberry) has 7 facets and Ztilde_{1,3} (octahedron) has 8. Thus the formula is not counting facets of the constructed truncated polytopes, or, if it counts facets of the original zonotope Z_{n,m}, it cannot distinguish the truncated polytopes. The advertised lower bound 2^{floor((N-1)/2)} is therefore unsupported and should be corrected or removed.
- [§3.3.2, Lemma 3.3.9 and Theorem 3.3.10] The proof of Lemma 3.3.9 is only a one-line reference to the ordered-partition description of faces of a graphical zonotope. This lemma is load-bearing: Theorem 3.3.10 uses it to identify the subgraph ED_uv for the truncated polytopes with the 1-skeleton of the contracted graphical zonotope, and then applies Balinski's theorem to conclude that this graph remains connected after deleting one or two vertices. What needs to be shown explicitly is that the uv-edge graph of Zbar_{n,m} and Ztilde_{n,m} is obtained from the 1-skeleton of Z_{K_{n,m}/uv} by deleting exactly the vertex or vertices corresponding to the deep truncation(s), and that those deleted vertices are genuine vertices of that 1-skeleton. As written, the decisive step is asserted rather than proved.
minor comments (4)
- [§3.3, Example 3.3.1] The table lists Ztilde_{2,2} as 'cuboctahedron' with f-vector (13,24,13), but the standard cuboctahedron has f-vector (12,24,14). If the polytope intended is not the usual cuboctahedron, the name should be changed or qualified.
- [§3.3, Corollary 3.3.5] The phrase 'the number of facets of Z_{n,m}' is ambiguous: it should say explicitly whether it refers to the original zonotope, Zbar_{n,m}, or Ztilde_{n,m}. The proof also silently treats the two truncated polytopes as non-isomorphic without giving a distinguishing invariant for the pair.
- [§3.3, Theorem 3.3.4] Theorem 3.3.4 states 'not isomorphic to matroid polytopes', while Theorem 3.3.13 establishes the stronger property of not being normally equivalent to a matroid polytope. It would be clearer to state the stronger property in Theorem 3.3.4 and in Corollary 3.3.5.
- [§3.3.2] The notation distinguishing ED_uv, ED_uv, and ED_uv is difficult to read in the typeset version. Please use visibly distinct symbols and reintroduce them at the point where they are used in the proof of Theorem 3.3.10.
Circularity Check
No load-bearing circularity; the main indecomposability criterion and the truncated-zonotope applications are derived from cycle equations and independent external theorems.
full rationale
The core derivation is self-contained. DC(F) is defined directly by cycle equations (Lemma 2.1.2), and Theorem 2.6.4 is proved by constructing a dilation of F from a dependent vertex set S and a covering family of flats, using Lemma 2.6.3; it never assumes the desired indecomposability. Theorem 2.5.4 is an implication from paths of dependent implicit edges to completeness of ED(F), with the base case of triangles computed from the cycle equations (Example 2.2.2). The proof does not invert the equivalence so as to assume indecomposability. The main application, Theorem 3.3.10, relies on Lemma 3.3.9, an explicit combinatorial identification with the 1-skeleton of the contracted graphical zonotope, and on Balinski's theorem; both are independent of the conclusion. The a-edges are shown dependent from parallelograms and triangles, not assumed dependent as a form of the target result. External inputs used—Shephard's theorem, Balinski's theorem, Oxley's fundamental-graph lemma, and the GGMS characterization—are standard and not derived from the paper's own claims. The self-citations [LPP25], [PPP25], and [PP25] appear in comparisons, remarks, or as a side characterization in Example 4.3.6 whose 'if' direction the paper itself proves; none is load-bearing for Theorem 2.6.4 or Theorem 3.3.4. I do flag a non-circular correctness gap: the facet-count formula in Corollary 3.3.5, '2^N+N+2−(2^n+2^{N−n})', contradicts the paper's own Example 3.3.1, where Z_{1,3} has 7 facets, not 12. Thus the quantitative lower bound 2^floor((N−1)/2) is not established by the argument as written, although this does not make the derivation circular and does not affect the existence statement in Theorem 3.3.4.
Assumptions & free parameters
assumptions (5)
- standard math Shephard-Kallay equivalence between polytope deformations and framework deformations (Lemma 2.1.4).
- standard math Balinski's theorem: the graph of a d-polytope is d-connected.
- domain assumption Matroid base polytopes are exactly deformed permutahedra with 0/1-coordinates (GGMS87).
- domain assumption For a connected matroid, its fundamental graph with respect to any base is connected (Oxl11, Prop. 4.3.2).
- standard math Known face description of graphical zonotopes in terms of ordered partitions and acyclic orientations.
Cite this review
Pith. "Pith review of The graph of implicit edge dependencies for indecomposability and beyond." pith.science (2026). https://pith.science/paper/G4SCDXYA
@misc{pith2026251205307,
author = {Pith},
title = {Pith review of: The graph of implicit edge dependencies for indecomposability and beyond},
year = {2026},
howpublished = {\url{https://pith.science/paper/G4SCDXYA}},
note = {Machine review of arXiv:2512.05307}
}
read the original abstract
A polytope is called indecomposable if it cannot be expressed nontrivially as a Minkowski sum of other polytopes. Since Gale introduced the concept in 1954, several increasingly strong criteria have been developed to characterize indecomposability. In this paper, we introduce a new approach to indecomposability for frameworks and polytopes based on the graph of implicit edge dependencies, which records proportionalities between edge lengths across all deformations. This yields a new indecomposability criterion that unifies and generalizes most previous approaches, and has additional consequences in the study of deformation cones. As a main application, we construct new indecomposable deformed permutahedra that are not matroid polytopes. In 1970, Edmonds already noted the difficulty of characterizing the extreme rays of the submodular cone, equivalently, indecomposable deformed permutahedra. Matroid polytopes of connected matroids form a well-known family of such examples. We exhibit a new infinite family of indecomposable deformations of the permutahedron, not arising from matroid polytopes, obtained by suitable truncations of certain graphical zonotopes. We further demonstrate the scope of our methods through several additional applications. In particular, we refute a conjecture of Smilansky (1987) on the relation between the numbers of vertices and facets of indecomposable polytopes. Moreover, we obtain new bounds on the dimensions of deformation cones and we construct and analyze uniquely decomposable polytopes.
Forward citations
Cited by 1 Pith paper
-
Minkowski decomposability of symmetric edge polytopes
P_G^± is Minkowski decomposable if and only if G is K_n, K_{2,n−2}, or K_{1,1,n−2}.
Reference graph
Works this paper leans on
-
[7]
arXiv:2510.03177. [McM87] Peter McMullen. Indecomposable convex polytopes.Israel J. Math., 58(3):321–323,
-
[1970]
Irreducible convex sets
[Gal54] David Gale. Irreducible convex sets. InProc. of the ICM, Amsterdam, 1954, Vol. 2, pages 217–218. Erven P. Noordhoff N. V ., Groningen,
1954
-
[1987]
The cone of semimodular rank functions
[GHSZ95] Eberhard Girlich, Michael Höding, Gabriele Schneidereit, and Alexander Zaporozhets. The cone of semimodular rank functions. In Ulrich Derigs, Achim Bachem, and Andreas Drexl, editors,Operations Research Proceedings 1994, pages 98–102, Berlin, Heidelberg,
1994
-
[2008]
42 [GL01] Shu Hong Gao and Alan G
Reprint of the 1994 edition. 42 [GL01] Shu Hong Gao and Alan G. B. Lauder. Decomposition of polytopes and polynomials.Discrete Comput. Geom., 26(1):89– 104,
1994
-
[2016]
arXiv:1612.06599. [Zie98] Günter M. Ziegler.Lectures on Polytopes, volume 152 ofGraduate texts in Mathematics. Springer-Verlag, New York,
-
[2023]
arXiv:2303.05751. [Joh66] Norman W. Johnson. Convex polyhedra with regular faces.Canadian J. Math., 18:169–200,
-
[2024]
[BLS+99] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M
arXiv:2311.16022. [BLS+99] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler.Oriented matroids, volume 46 ofE. of Math. and its Applications. Cambridge University Press, 2nd ed edition,
-
[2025]
[BC] Spencer Backman and Federico Castillo
arXiv:2505.14338. [BC] Spencer Backman and Federico Castillo. Polytopal bases for barycentric subdivisions. Manuscript in preparation. [BGH24] Gaston Burrull, Tao Gui, and Hongsheng Hu. Strongly dominant weight polytopes are cubes,
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.