Pith. sign in

REVIEW 2 major objections 4 minor 13 references

Minkowski decomposability of symmetric edge polytopes

T0 review · 2 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Symmetric edge polytopes decompose exactly for three complete multipartite graphs.

desk verdict The classification is almost certainly correct and the proof outline is sound, but the omitted verification in Lemma 4.2(b)–(e) is an expositional gap that should be fixed before publication. read the letter →

arxiv 2608.02445 v1 pith:VDKW3P3T submitted 2026-08-03 math.CO

Akihiro Higashitani , Aki Mori This is my paper · ORCID
classification math.CO MSC 52B1252B2005C75
keywords Minkowskidecomposabilitysymmetricedgepolytopescompletemultipartitegraphstriangularfaceslattice2-connectedpolytopeindecomposability
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

A polytope is Minkowski decomposable when it can be written as the set of all sums q+r with q in one polytope and r in another, neither a mere scaled copy of the original. The paper settles this question completely for symmetric edge polytopes, the convex hulls of differences e_i−e_j coming from the edges of a graph. The central claim is that a connected graph's symmetric edge polytope is Minkowski decomposable exactly for three complete multipartite graphs: K_n, K_{2,n−2}, and K_{1,1,n−2}. For every other connected graph the polytope is indecomposable. The proof characterizes triangular faces as triples of directed edges obeying three conditions, assembles these triangles into a strongly connected family touching every facet for every non-exceptional 2-connected graph, and gives explicit decompositions for the three exceptions.

What carries the argument

The central object is the symmetric edge polytope P_G± = conv{±(e_i−e_j) : {i,j} in E(G)}, a centrally symmetric lattice polytope in the hyperplane sum x_i = 0. The load-bearing mechanism is the set T(G) of triples of directed edges satisfying conditions (A1), (A2), and (A3); by the paper's Proposition 2.2, exactly these triples give triangular faces. The proof then uses transitions between such triples, swapping one directed edge at a time, to build a strongly connected family of triangular faces that touches every facet. Together with the paper's Theorem 3.2, a standard criterion saying that a polytope with such a family is indecomposable, this forces indecomposability. The only graphs for

What would settle it

Take a small 2-connected graph not isomorphic to the three exceptional families, compute the set T(G) of directed-edge triples satisfying (A1)–(A3), and check whether the displayed sequences in Lemma 4.2(b)–(e) remain inside T(G) at every step; a single violation would invalidate the proof. For the theorem itself, a connected graph outside the three families whose P_G± admits a nontrivial Minkowski decomposition would refute the classification.

Watch

Extended reading notes

Core claim

The discovery, on the paper's own terms, is a complete classification: for a connected graph G with at least three vertices, the symmetric edge polytope P_G± is Minkowski decomposable if and only if G is K_n, K_{2,n−2}, or K_{1,1,n−2}. The engine of the proof is a characterization of the two-dimensional faces: a triple of directed edges forms a triangular face exactly when it contains no opposite pair, no two of its edges lie on a directed cycle of length 3 or 4, and the three edges are not together on a directed cycle of length 5 or 6. Using this characterization, the paper shows that every 2-connected graph outside the three exceptional families has a strongly connected family of triangula

Load-bearing premise

The load-bearing premise is that Lemma 4.2's five local transitions are all valid: the paper verifies case (a) and asserts that cases (b)–(e) 'can be verified in the same way' without supplying the verification, and the only-if direction of the main classification depends on every one of those transitions staying inside the set of valid triangular faces.

Editorial extensions

If this is right

  • For every connected graph outside the three families, P_G± is Minkowski indecomposable, including all non-2-connected graphs and all cycles of length at least 5.
  • The exceptional graphs are exactly those attaining equality in a sharp lower bound on the number of edges of P_G± proved in a separate result, a coincidence the paper highlights as evidence of a common mechanism.
  • The complete graph decomposition P_K_n± = Δ_{n−1} + (−Δ_{n−1}) expresses the polytope as a sum of a simplex and its negative, showing that one exceptional family decomposes in the simplest possible way.
  • For K_{2,n−2} and K_{1,1,n−2}, the explicit decompositions make the classification constructive: the summands are written down, not merely asserted to exist.
  • The triangular-face characterization gives a finite, checkable list of conditions for when three vertices of P_G± form a face, which can be reused in further studies of the polytope's face structure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the classification is right, Minkowski indecomposability is the generic behavior for symmetric edge polytopes: the decomposable cases sit at three high-symmetry complete multipartite families, so almost every connected graph yields an indecomposable polytope.
  • The appearance of the same three families in the edge-count lower-bound result suggests a possible principle: for symmetric edge polytopes, Minkowski decomposability may occur exactly when the one-dimensional face structure is as sparse as allowed; testing whether this principle extends to related polytope classes would be a natural next step.
  • The four local transitions in Lemma 4.2 stated without detailed verification are the natural place to stress-test the proof; a computer search over small 2-connected graphs checking that every displayed triple satisfies (A1)–(A3) would either confirm the classification or expose a gap.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper gives a complete classification of Minkowski decomposability for symmetric edge polytopes of connected graphs: for a connected graph G with n ≥ 3, P_G^± is Minkowski decomposable if and only if G is isomorphic to K_n, K_{2,n-2}, or K_{1,1,n-2}. The proof uses a graph-theoretic description of triangular faces (Conditions (A1)-(A3)), McMullen's indecomposability criterion via strongly connected families of triangular faces touching all facets, and a transition analysis showing that every 2-connected non-exceptional graph has a 'good' vertex. Explicit Minkowski decompositions are provided for the three exceptional families.

Significance. If correct, the result is a clean and satisfying classification. It connects Minkowski decomposability of symmetric edge polytopes to earlier work on edge counts, and the use of McMullen's criterion is well suited to the problem. The explicit decompositions in Section 5 and the facet-subgraph argument in Section 6 are valuable. The main combinatorial engine, Proposition 4.1, is structurally convincing, but its correctness is contingent on Lemma 4.2(b)-(e), whose verification is asserted rather than supplied. This is a genuine, load-bearing gap, although my own spot-checks of the displayed transitions did not reveal an actual error.

major comments (2)
  1. [§4, Lemma 4.2(b)-(e)] The five local-switch cases (b)-(e) are used repeatedly in Proposition 4.1 to force the three exceptional graphs when no good vertex exists. For each case the paper displays a transition sequence and states only that validity 'can be verified in the same way as in (a)'. No verification of Conditions (A2) or (A3) for the intermediate triples is provided. Since Proposition 4.1 is the heart of the 'only if' direction of Theorem 1.1, any invalid intermediate triple would break the good-vertex argument and the classification. This is not a stylistic matter. The authors should give a complete proof, or at least a table of pairwise (A2)/(A3) checks for every intermediate triple in cases (b)-(e), including the three subcases of (d).
  2. [§4, Proposition 4.1 (case V(G)\N_G[u] nonempty)] The application of Lemma 4.2(d) at the point 'If some a ∈ N_G(w)∩N_G(u) had a neighbour in N_G(u)' assumes the existence of the vertex b in the statement of Lemma 4.2(d). In the application this b exists because N_G(w)∩N_G(u) has at least two elements and |N_G(u)| ≥ 3, but the lemma as stated should justify the choice 'Choose b ∈ N_G(u)\setminus{a,c} so that wb∈E(G) or wc∈E(G)'. Without this clarification, the three cases in (d) do not cover all possibilities as cleanly as claimed.
minor comments (4)
  1. [§2, Proposition 2.2 proof] In the displayed definition of c(e), the middle line should read '1, e ∈ T' (i.e., the reverse directed edge lies in T). As typeset, it is indistinguishable from the first line.
  2. [§3, Proposition 3.4] The connectedness argument for the sign patterns is compressed, particularly for n = 5, 6. The statement that it is enough to consider sign patterns for a fixed I after 'ignoring signs' should say explicitly that adjacency between triples with different underlying index sets preserves two signs. This is true, but it is not immediate from the Johnson graph sentence alone.
  3. [§3, Corollary 3.3] The proof uses two nontrivial facts without elaboration: that facets of a free sum of symmetric edge polytopes are joins of facets of the summands, and that [10, Theorem 3] applies to make these facets indecomposable. A sentence or precise reference for each would help the reader.
  4. [§6, proof of Theorem 1.1] The claim 'Every such directed edge belongs to some member of F^- ∪ F^+' relies on deg(u) ≥ 3. This is true in the application, but it could be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the classification is derived from external criteria and explicit polytope decompositions; the skeptical concern is a proof-completeness gap, not a circular reduction.

full rationale

The paper's derivation chain is not circular. Proposition 2.2 characterizes triangular faces via the external edge-pair criterion of Codenotti–Riccardi–Venturello [2, Lemma 3.2] and a feasibility theorem for difference constraints; its proof is self-contained once these external facts are granted. McMullen's indecomposability criterion [10] and the facet-subgraph description [1, Theorem 3(2)] are also external supporting results, not restatements of Theorem 1.1. Proposition 4.1 is a graph-theoretic dichotomy that produces a 'good vertex' unless the graph is one of K_n, K_{2,n-2}, K_{1,1,n-2}; the argument uses local switch sequences asserted in Lemma 4.2. The paper explicitly verifies case (a) and says cases (b)-(e) 'can be verified in the same way as in (a).' This is a terseness or verification gap, potentially load-bearing for correctness, but it is not circularity: the displayed transitions are claimed consequences of the defining conditions (A1)-(A3), not assumptions equivalent to the theorem. The exceptional families are shown decomposable by explicit Minkowski sums in Section 5, and the 'only if' direction uses the external facet description and McMullen's theorem. Remark 1.2 merely notes that the exceptional families coincide with those in [2]; this coincidence is not used as evidence. Self-citations such as [6], [8], and [9] supply context or standard structural facts and do not carry the main classification. Thus no step reduces to its own input by definition or by self-citation, and the honest finding is no significant circularity, score 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters or invented entities; the proof imports standard criteria (McMullen) and prior structural theorems on symmetric edge polytopes ([1], [2], [9]).

assumptions (6)
  • standard math McMullen's criterion (Theorem 3.2): a polytope with a strongly connected family of indecomposable faces touching every facet is Minkowski indecomposable.
    Quoted from [10] and used as the central indecomposability tool in Sections 3, 4, and 6.
  • domain assumption Characterization of edges of symmetric edge polytopes (Codenotti–Riccardi–Venturello [2, Lemma 3.2]): two vertices span an edge iff the corresponding directed edges are not in a common directed cycle of length 3 or 4.
    Used in Proposition 2.2 to establish (A2) and in the local-switch verification.
  • domain assumption Facet-subgraph description (Chen–Davis–Korchevskaia [1, Theorem 3(2)]): the directed edges whose vertices lie on a given facet form a connected spanning subgraph of G.
    Used in Section 6 to prove that the triangle family touches every facet.
  • domain assumption Free sum decomposition for symmetric edge polytopes of 2-connected components [9].
    Used in Corollary 3.3 for non-2-connected graphs.
  • standard math Difference-constraints feasibility theorem (Cormen–Leiserson–Rivest–Stein).
    Used in Proposition 2.2 to construct the linear functional defining the triangular face.
  • standard math The Johnson graph J(n,3) is connected.
    Used in Proposition 3.4 to show T(G) is connected for cycles.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Minkowski decomposability of symmetric edge polytopes." pith.science (2026). https://pith.science/paper/VDKW3P3T

@misc{pith2026260802445,
  author       = {Pith},
  title        = {Pith review of: Minkowski decomposability of symmetric edge polytopes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VDKW3P3T}},
  note         = {Machine review of arXiv:2608.02445}
}
abstract

In this paper, we study the Minkowski decomposability of symmetric edge polytopes $P_G^\pm$ of a finite simple graph $G$ on vertex set $[n]$. More precisely, we give a complete characterization of graphs whose symmetric edge polytopes are Minkowski decomposable. We prove that $P_G^\pm$ is Minkowski decomposable if and only if $G$ is one of the three complete multipartite graphs: $K_n$, $K_{2,n-2}$, or $K_{1,1,n-2}$. In other words, if $G$ does not belong to these three families, then $P_G^\pm$ is Minkowski indecomposable.

Figures

Figures reproduced from arXiv: 2608.02445 by the authors.

Figure 1
Figure 1. The five local configurations in Lemma 4.2. Solid edges indicate edges of G, and dashed edges indicate non-edges. Proof. (a): Let a = x0, x1, . . . , xℓ = c be a shortest path in G − u, with ℓ ≥ 3. Put y = xℓ−1. Thus, yc ∈ E(G). If y ∈ NG(u), let b = y; otherwise choose b ∈ NG(u) \ {a, c}. Consider the sequence {au, bu, cu} → {au, bu, yc} → {au, uc, yc} → {ua, uc, yc} → {ua, ub, uc}. Each step changes exactly one di… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 4 linked inside Pith

  1. [1]

    T. Chen, R. Davis, and E. Korchevskaia, Facets and facet subgraphs of symmetric edge polytopes, Discrete Appl. Math.328(2023), 139–153

    2023

  2. [2]

    Codenotti, R

    G. Codenotti, R. Riccardi, and L. Venturello, The number of edges of a symmetric edge polytope, arXiv:2512.16572, (2025)

    arXiv 2025

  3. [3]

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,Introduction to Algorithms, third edition, MIT Press, Cambridge, MA, 2009

    2009

  4. [4]

    D’Al ` ı, M

    A. D’Al ` ı, M. Juhnke-Kubitzke, D. K¨ ohne, and L. Venturello, On the gamma-vector of symmetric edge polytopes,SIAM J. Discrete Math.37(2023), no. 2, 487–515

    2023

  5. [5]

    Ferroni, Symmetric edge polytopes are not gamma-positive, arXiv:2607.02424, (2026)

    L. Ferroni, Symmetric edge polytopes are not gamma-positive, arXiv:2607.02424, (2026)

    arXiv 2026

  6. [6]

    Higashitani, Smooth Fano polytopes arising from finite directed graphs,Kyoto J

    A. Higashitani, Smooth Fano polytopes arising from finite directed graphs,Kyoto J. Math.55(2015), no. 3, 579–592

    2015

  7. [7]

    Higashitani, K

    A. Higashitani, K. Jochemko, and M. Micha lek, Arithmetic aspects of symmetric edge polytopes, Mathematika65(2019), 763–784

    2019

  8. [8]

    Higashitani, A

    A. Higashitani, A. Padrol, and R. Sanyal, Indecomposability of 0/1-polytopes, arXiv:2605.22594, (2026)

    arXiv 2026

Show all 13 references
  1. [9]

    Matsui, A

    T. Matsui, A. Higashitani, Y. Nagazawa, H. Ohsugi, and T. Hibi, Roots of Ehrhart polynomials arising from graphs,J. Algebraic Combin.34(2011), no. 4, 721–749

    2011

  2. [10]

    McMullen, Indecomposable convex polytopes,Israel J

    P. McMullen, Indecomposable convex polytopes,Israel J. Math.58(1987), no. 3, 321–323

    1987

  3. [11]

    Ohsugi and A

    H. Ohsugi and A. Tsuchiya, Theh ∗-polynomials of locally anti-blocking lattice polytopes and their γ-positivity,Discrete & Comput. Geom.,66, (2021), 701–722

    2021

  4. [12]

    Padrol and G

    A. Padrol and G. Poullot, The graph of implicit edge dependencies for indecomposability and beyond, arXiv:2512.05307, (2025)

    2025 arXiv

  5. [13]

    G. C. Shephard, Decomposable convex polyhedra,Mathematika10(1963), 89–95. Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Osaka University, Suita, Osaka 565-0871, Japan Email address:higashitani@ist.osaka-u.ac.jp Center for Ph...

    1963

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.