pith. sign in

arxiv: 2409.11970 · v2 · submitted 2024-09-18 · 🧮 math.CO

Proof of a conjecture on graph polytope

Feihu Liu This is my paper

Pith reviewed 2026-05-23 21:06 UTC · model grok-4.3

classification 🧮 math.CO
keywords graph polytopeEhrhart seriespalindromic polynomialhypergraph polytopeunimodular polytopeinteger polytopeStanley's reciprocity theorem
0
0 comments X

The pith

For any simple connected graph, the numerator polynomial of the Ehrhart series of its graph polytope is palindromic.

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

The paper proves a conjecture that the numerator polynomial of the Ehrhart series of the graph polytope is palindromic whenever the underlying graph is simple and connected. The proof applies Stanley's reciprocity theorem to the Ehrhart series. The work also introduces hypergraph polytopes, shows that simple connected unimodular hypergraph polytopes are integer polytopes, and proves that simple connected uniform hypergraph polytopes likewise have palindromic Ehrhart numerators.

Core claim

We prove that for any simple connected graph the numerator polynomial of the Ehrhart series of its graph polytope is palindromic, using Stanley's reciprocity theorem. We introduce hypergraph polytopes and establish that every simple, connected, unimodular hypergraph polytope is an integer polytope. Additionally, for simple connected uniform hypergraph polytopes we demonstrate that the numerator polynomial of their Ehrhart series is palindromic.

What carries the argument

Graph polytope from vertex-weighted graphs, whose Ehrhart series numerator polynomial is shown to be palindromic via Stanley's reciprocity theorem.

If this is right

  • The Ehrhart series numerator is palindromic for the graph polytope of every simple connected graph.
  • Every simple connected unimodular hypergraph polytope is an integer polytope.
  • The Ehrhart series numerator is palindromic for every simple connected uniform hypergraph polytope.

Where Pith is reading between the lines

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

  • The palindromicity implies a symmetry in the enumeration of lattice points inside successive dilates of these polytopes.
  • Similar palindromicity results may hold for other combinatorial polytopes constructed from hypergraphs or other set systems.
  • The unimodularity hypothesis on hypergraph polytopes might be replaceable by a weaker combinatorial condition.

Load-bearing premise

Stanley's reciprocity theorem applies directly to the Ehrhart series of the graph polytope without requiring further conditions on the weighting or the specific form of the polytope beyond the graph being simple and connected.

What would settle it

A simple connected graph whose Ehrhart series numerator polynomial is not palindromic would disprove the main claim.

Figures

Figures reproduced from arXiv: 2409.11970 by Feihu Liu.

Figure 1
Figure 1. Figure 1: An unimodular hypergraph We can easily verify that matrix A is totally unimodular, and H is a unimodular hypergraph. It is clear that H is not uniform hypergraph. We can compute Ehr(P(H), x) using the package LattE [6], and the CTEuclid package [16]. We obtain Ehr(P(H), x) = 1 + 6x + 4x 2 (1 − x) 6 [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A 3-uniform hypergraph Example 3.3. Let H = (V, E∗ = {e1, e2, e3}) be the hypergraph in [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
read the original abstract

Graph polytopes arising from vertex-weighted graphs were first introduced by B\'ona, Ju, and Yoshida. We prove a conjecture stating that for any simple connected graph, the numerator polynomial of the Ehrhart series of its graph polytope is palindromic, using Stanley's reciprocity theorem. Furthermore, we introduce hypergraph polytopes and establish that every simple, connected, unimodular hypergraph polytope is an integer polytope. Additionally, for simple connected uniform hypergraph polytopes, we demonstrate that the numerator polynomial of their Ehrhart series is palindromic.

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

2 major / 2 minor

Summary. The manuscript proves the conjecture that for any simple connected graph the numerator polynomial of the Ehrhart series of its graph polytope is palindromic, by direct appeal to Stanley's reciprocity theorem. It introduces the notion of hypergraph polytopes, proves that every simple connected unimodular hypergraph polytope is an integer polytope, and shows that the numerator polynomial is likewise palindromic for simple connected uniform hypergraph polytopes.

Significance. If the invocation of Stanley's reciprocity is fully justified, the work resolves the stated conjecture on graph polytopes and supplies the first results on Ehrhart series for the newly defined hypergraph polytopes. The extension from graphs to hypergraphs is a natural and potentially useful contribution to the study of weighted polytopes.

major comments (2)
  1. [Proof of the graph-polytope conjecture (invocation of Stanley reciprocity)] The central argument applies Stanley's reciprocity theorem to deduce palindromicity of the numerator after clearing the denominator (1-t)^{d+1}. However, reciprocity alone yields a functional equation relating the series of the polytope and its relative interior; palindromicity of the numerator holds if and only if the polytope is Gorenstein (or satisfies the equivalent condition that its canonical module is generated in degree 1). The manuscript does not verify that the graph polytope (defined via the given vertex-weighting) meets this condition, nor does it confirm that the weighting and facet description preserve the Gorenstein property for arbitrary simple connected graphs. This verification is load-bearing for the main claim.
  2. [Results on uniform hypergraph polytopes] The same gap appears for the uniform hypergraph polytopes: the palindromicity statement again rests on Stanley reciprocity without an explicit check that these polytopes are Gorenstein. If a counter-example exists among simple connected uniform hypergraphs, the claim would fail.
minor comments (2)
  1. [Abstract] The abstract introduces the term 'hypergraph polytope' without a one-sentence definition; a brief parenthetical description would improve readability for readers unfamiliar with the new construction.
  2. [Introduction / Definitions] Notation for the vertex-weighting function and the resulting polytope is introduced without an explicit comparison table to the earlier Bóna-Ju-Yoshida definition; adding such a table would clarify the extension.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for pointing out the need to explicitly verify the Gorenstein property when applying Stanley's reciprocity theorem. We address the major comments below and will revise the manuscript to close this gap.

read point-by-point responses

  1. Referee: [Proof of the graph-polytope conjecture (invocation of Stanley reciprocity)] The central argument applies Stanley's reciprocity theorem to deduce palindromicity of the numerator after clearing the denominator (1-t)^{d+1}. However, reciprocity alone yields a functional equation relating the series of the polytope and its relative interior; palindromicity of the numerator holds if and only if the polytope is Gorenstein (or satisfies the equivalent condition that its canonical module is generated in degree 1). The manuscript does not verify that the graph polytope (defined via the given vertex-weighting) meets this condition, nor does it confirm that the weighting and facet description preserve the Gorenstein property for arbitrary simple connected graphs. This verification is load-bearing for the main claim.

    Authors: We agree that the manuscript applies Stanley's reciprocity without an explicit check that the graph polytopes are Gorenstein. The vertex-weighted construction from simple connected graphs is intended to produce polytopes whose Ehrhart series satisfy the required functional equation for palindromicity, but this is not verified in the current text. We will add a lemma establishing that these polytopes are Gorenstein (using the facet description and weighting to show the canonical module is generated in degree 1), thereby justifying the direct appeal to reciprocity. revision: yes

  2. Referee: [Results on uniform hypergraph polytopes] The same gap appears for the uniform hypergraph polytopes: the palindromicity statement again rests on Stanley reciprocity without an explicit check that these polytopes are Gorenstein. If a counter-example exists among simple connected uniform hypergraphs, the claim would fail.

    Authors: The referee is correct that the same omission occurs for the uniform hypergraph polytopes. We will extend the new Gorenstein verification to this setting, leveraging the unimodularity and uniformity conditions already proved in the manuscript to confirm that the canonical module is generated in degree 1. This will support the palindromicity claim for these polytopes as well. revision: yes

Circularity Check

0 steps flagged

No circularity; central claim rests on external Stanley reciprocity theorem

full rationale

The paper states it proves the palindromicity conjecture for graph polytopes by direct application of Stanley's reciprocity theorem (an independent, externally established result on Ehrhart series). No self-definitional loops, fitted parameters renamed as predictions, or load-bearing self-citations appear in the derivation chain. The additional results on hypergraph polytopes are presented as new establishments without reducing to prior inputs by construction. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The claims rest on the applicability of Stanley's reciprocity theorem and on the newly introduced definition of hypergraph polytopes; no numerical parameters are fitted.

axioms (1)
  • standard math Stanley's reciprocity theorem applies to the Ehrhart series of graph polytopes and hypergraph polytopes
    Invoked in the abstract to establish palindromicity
invented entities (1)
  • hypergraph polytope no independent evidence
    purpose: Generalization of graph polytope to hypergraphs
    New object defined in the paper to extend the palindromicity and integrality results

pith-pipeline@v0.9.0 · 5603 in / 1279 out tokens · 28851 ms · 2026-05-23T21:06:16.229946+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

19 extracted references · 19 canonical work pages · 1 internal anchor

  1. [1]

    Baldoni-Silva, J

    W. Baldoni-Silva, J. A. De Loera, and M. Vergne, Counting integer flows in networks , Found. Comput. Math. 4 (2004), 277–314

    work page 2004

  2. [2]

    Beck and S

    M. Beck and S. Robins, Computing the continuous discretely, in: Integer-Point Enumeration in Polyhedra, second edition, Undergraduate Texts in Mathematics. Springer, New York, (2015)

    work page 2015

  3. [3]

    B´ ona and H.-K

    M. B´ ona and H.-K. Ju,Enumerating solutions of a system of linear inequalities related to magic squares, Ann. Comb. 10 (2006), 179–191

    work page 2006

  4. [4]

    B´ ona, H.-K

    M. B´ ona, H.-K. Ju, and R. Yoshida, On the enumeration of certain weighted graphs , Discrete Appl. Math. 155 (2007), 1481–1496

    work page 2007

  5. [5]

    Bretto, Hypergraph Theory, Mathematical Engineering

    A. Bretto, Hypergraph Theory, Mathematical Engineering. Springer, New York, (2013)

    work page 2013

  6. [6]

    J. A. De Loera, R. Hemmecke, J. Tauzer, and R. Yoshida, Effective lattice point counting in rational convex polytopes, J. Symbolic Comput. 38 (2004), 1273–1302

    work page 2004

  7. [7]

    Ehrhart, Sur les polyh´ edres rationnels homoth´ etiques ´ an dimensions, C

    E. Ehrhart, Sur les polyh´ edres rationnels homoth´ etiques ´ an dimensions, C. R. Acad Sci. Paris. 254 (1962), 616–618

    work page 1962

  8. [8]

    H.-K. Ju, S. Kim, and D. Lee, Different volume computational methods of graph polytopes , Bull. Korean Math. Soc. 55 (2018), 1405–1417

    work page 2018

  9. [9]

    Ju, Enumeration of weighted complete graphs, J

    H.-K. Ju, Enumeration of weighted complete graphs, J. Korean Math. Soc. 44 (2007), 1351–1362

    work page 2007

  10. [10]

    An Extension of hibi's palindromic theorem

    D. Lee and H.-K. Ju, An extension of Hibi’s palindromic theorem , arXiv. 1503.05658, (2015)

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  11. [11]

    R. P. Stanley, Linear homogeneous diophantine equations and magic labelings of graphs , Duke Math, J. 40 (1973), 607–632

    work page 1973

  12. [12]

    R. P. Stanley, Combinatorial reciprocity theorems, Advances in Math. 14 (1974), 194–253

    work page 1974

  13. [13]

    R. P. Stanley, Decompositions of rational convex polytopes, Ann. Discrete Math. 6 (1980), 333– 342

    work page 1980

  14. [14]

    R. P. Stanley, Enumerative Combinatorics (volume 1) , Cambridge Studies in Advanced Mathe- matics, vol. 49, Cambridge University Press, (2012)

    work page 2012

  15. [15]

    Xin, A generalization of Stanley’s monster reciprocity theorem , J

    G. Xin, A generalization of Stanley’s monster reciprocity theorem , J. Combin Theory, Series A. 114(8) (2007), 1526–1544

    work page 2007

  16. [16]

    Xin, A Euclid style algorithm for MacMahon’s partition analysis , J

    G. Xin, A Euclid style algorithm for MacMahon’s partition analysis , J. Combin Theory, Series A. 131 (2015), 32–60

    work page 2015

  17. [17]

    Xin and Y

    G. Xin and Y. Zhong Proving some conjectures on Kekul´ e numbers for certain benzenoids by using Chebyshev polynomials , Adv. in Appl. Math. 145 (2023), No. 102479

    work page 2023

  18. [18]

    G. Xin, Y. Zhong, and Y. Zhou, On magic labellings of pseudo-cycle graphs and pseudo-line graphs, in preparation

    work page

  19. [19]

    G. M. Ziegler, Lectures on Polytopes, Grad. Texts Math. 152, Springer-Verlag, New York (1995). School of Mathematical Sciences, Capital Normal University, Beijing 100048, PR China Email address : liufeihu7476@163.com

    work page 1995