REVIEW 2 major objections 4 minor 9 references
Three Combinatorial Algorithms for the Cave Polynomial of a Polymatroid
T0 review · 2 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read This paper proves that four polynomials attached to a polymatroid — the cave, stalactite, box, and Möbius polynomials — coincide, and gives a fully combinatorial proof via an explicit Möbius formula and a stalactite-counting recurrence.
desk verdict Solid combinatorial re-proof of a known equality, but Definition 1.3 has a concrete bug that must be fixed before the paper is publishable. 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 engine is the M-convex exchange property of the polymatroid base set (Definition 2.2): for any u,v in the base and coordinate i with u_i > v_i, there exists j with u_j < v_j such that u − e_i + e_j remains in the base. This guarantees that every base element other than the first in a lexicographic order has at least one lexicographically earlier neighbor. That neighbor existence makes the signed sum of contributions from a single stalactite telescope to zero (and to 1 for the first element), which is what forces the stalactite counts to obey the Möbius recurrence. The truncation P_n = P ∩ (n + ℕ^p) is again a polymatroid, and Lemma 4.2 shows stalactite counts are unchanged under truncati
What would settle it
For the uniform matroid U_{2,3} on ground set [3], whose base set is {(1,1,0),(1,0,1),(0,1,1)}, compute c_n(P) by direct stalactite enumeration in the lex order and by the recurrence c_n(P) = 1 − Σ_{m>n} c_m(P) for every n in the independence polytope. Any mismatch between the two lists refutes Theorem 1.7 and hence Theorem 1.5.
Extended reading notes
Core claim
The paper establishes the four-way identity cave_P(t) = Stal_P(t) = Box_P(t) = Möb_P(t) for every polymatroid P. The proof shows that the signed number of stalactites containing a point n satisfies the Möbius recurrence c_n(P) = 1 − Σ_{m>n} c_m(P) (with c_n = 1 on the base polytope and 0 outside the independence polytope), so stalactite counts equal Möbius values. It also proves an explicit formula for the Möbius function of the independence poset: µ_P(m,n) = (−1)^j when n−m is a sum of j distinct coordinate vectors, and 0 otherwise. This makes the box polynomial equal to the Möbius polynomial coefficient by coefficient. A corollary gives Snapper_P(t) = b(Möb_P(t)) = b(Stal_P(t)), where b se
Load-bearing premise
The argument relies on the M-convex exchange property, which guarantees that every base element other than the first has a lexicographically earlier neighbor; if a set is homogeneous but not M-convex, the cancellation that makes stalactite counts equal Möbius values can fail.
Editorial extensions
If this is right
- The Snapper polynomial of a polymatroid can be obtained by applying the binomial-coefficient map b to either the Möbius or the stalactite polynomial, not just the box polynomial.
- The Möbius function of the independence poset has the closed form (−1)^j when n−m is a sum of j distinct unit vectors, making Möbius values computable by direct inspection.
- Stalactite counts satisfy the same recurrence as Möbius values, so they are independent of the chosen lexicographic order even though individual stalactites depend on it.
- Combining the three equalities yields a fully combinatorial proof of the identity between the cave polynomial and the Snapper polynomial, bypassing the algebraic-geometric flat-degeneration argument.
Reading between the lines
- Because the equality is purely combinatorial, the cave polynomial is likely a poset invariant of the independence polytope; other poset invariants, such as the order polynomial, might play analogous roles in K-theoretic computations.
- The explicit Möbius formula could be turned into an efficient algorithm for computing Grothendieck ring classes of multiplicity-free varieties in products of projective spaces, replacing algebraic geometry with a simple sign count.
- The proof isolates exactly which property makes the identity work: the M-convex neighbor-existence step. A weaker axiom that still guarantees every non-minimal base element has a lexicographically earlier neighbor would probably yield the same equality for a larger class of finite homogeneous sets.
- The running example shows the stalactite polynomial can be read off from the Hasse diagram of the independence poset, so one might test whether the stalactite polynomial is a complete invariant of that poset.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies three polynomials attached to a polymatroid P — the stalactite polynomial, the box polynomial, and the Möbius polynomial — and proves that they all coincide with the cave polynomial introduced in prior work. It gives an explicit closed formula for the Möbius function of the independence poset (Theorem 1.6 / 3.1), a Möbius-type recurrence for the number of stalactites containing a point (Theorem 1.7), and derives as an application that the Snapper polynomial equals b(Möb_P(t)) = b(Stal_P(t)) (Corollary 1.9). The proofs are intended to be elementary and combinatorial, using only the M-convexity of the base set, in contrast to earlier proofs that relied on algebraic geometry and K-theory.
Significance. If the results hold, the paper gives a self-contained combinatorial unification of four objects that previously appeared to require algebraic-geometric machinery to connect. The explicit Möbius formula and the recurrence for stalactite counts are concrete and potentially useful tools. The paper is clearly written, works through a running example, and the main combinatorial ideas are sound modulo the corrections below. The central claim, Theorem 1.5, is significant because it identifies the cave polynomial with the Snapper polynomial in a combinatorial way.
major comments (2)
- [Definition 1.3, Theorem 3.3, Example 3.4] The box polynomial is misdefined. With the displayed formula, the factor for any n_i=0 is t_i^0 - t_i^{max{0,-1}} = 1-1 = 0, so the whole term vanishes. This makes Example 3.4 and the coefficient comparison in Theorem 3.3 invalid: for the running example, the literal Box_P(t) would be t_1t_2^2 + t_1^2t_2 - t_2^2 - t_1t_2 - t_1^2 + 1, not Möb_P(t). The intended formula is clearly t_i^{n_i} - t_i^{n_i-1} with the convention t_i^{-1}=0 (equivalently, the factor is 1 when n_i=0). Please correct Definition 1.3 and adjust the proof of Theorem 3.3.
- [Theorem 4.3, Lemma 4.2] The reduction to the case n=0 via truncation needs an additional argument. Lemma 4.2 is stated only for m∈P_n, but the proof of Theorem 4.3 uses it to replace Σ_{m≥n} c'_m(P) by Σ_{m∈I(P_n)} c'_m(P_n). One must justify (i) I(P_n)∩{m≥n} = I(P)∩{m≥n} (equivalently, B(P_n) = B(P)∩{m≥n}) and (ii) c'_m(P_n)=0 for m not ≥n. Point (ii) follows because if m=a-e_J and m_i<n_i, then a_i=n_i and i∈J, which would force a previous neighbor of a with i-coordinate n_i-1<n_i, impossible since all points of P_n are ≥n. Please add these details or strengthen Lemma 4.2 to cover all m∈I(P) with m≥n.
minor comments (4)
- [Theorem 3.1] In the second case, the statement 'a∉B implies μ_P(m,a)=0 by induction' is correct but terse; the reader must verify that any a=m+e_J with J not⊆A fails the inequality a≤n.
- [Definition 2.8] Typo: 'A finite set C∈N^p' should be 'C⊆N^p'.
- [Example 3.4] The example silently uses the corrected box-polynomial definition; please align it explicitly with the corrected Definition 1.3.
- [Lemma 4.2] The proof asserts 'the same number of stalactites' but does not explicitly construct the bijection; it should note that, for the required directions, the lexicographic predecessor set in P_n is exactly the intersection of the predecessor set in P with P_n.
Circularity Check
No significant circularity; the four-way equality is proven by self-contained combinatorial arguments.
full rationale
The derivation chain is self-contained at the level of the paper's own definitions. Theorem 2.9 compares coefficients of the cave polynomial with stalactite membership, using only the combinatorial definitions of neighbors and stalactites. Theorem 3.1 proves the explicit Möbius formula by induction from the Möbius recurrence, and Theorem 3.3 expands the box product and identifies its coefficients with those Möbius values. Theorem 4.3 shows that the signed stalactite counts satisfy the same top-down recurrence as the Möbius values, using Lemma 4.2 and the M-convexity axiom; the key cancellation in the proof is a direct alternating binomial sum, not an imported conclusion. No parameter is fitted and no result is assumed as a prediction. The self-citation [CMS25] appears when recalling the cave polynomial and the Snapper-to-cave identity in Remark 1.8, but Corollary 1.9 also follows from the cited [EL23] identity Snapp_P = b(Box_P) together with Theorem 1.5, so [CMS25] is not load-bearing. Two manuscript issues noted in the text are correctness concerns rather than circularity: the literal Definition 1.3 factor t_i^0 - t_i^{max(0,-1)} = 0 would make box terms vanish for zero coordinates (contradicting Example 3.4 and Theorem 3.3's coefficient reading), and the assertion that the stalactite polynomial is independent of lex order is not separately proved. Neither issue makes the central derivation equivalent to its inputs by construction.
Assumptions & free parameters
assumptions (5)
- standard math Componentwise order on the integer points of an independence polytope is a finite poset with an adjoined maximum; Möbius inversion applies.
- standard math The M-convex set definition (Definition 2.2) is equivalent to the rank-function definition of a polymatroid.
- domain assumption M-convex exchange: for u,v in P with u_i>v_i, there exists j with u_j<v_j and u-e_i+e_j∈P.
- domain assumption The independence polytope I(P) contains all integer points coordinatewise below the top set by construction (Definition 2.5).
- standard math Lexicographic order is a total order on finite subsets of N^p; neighbor relations in the cave formula correspond to lex-smaller predecessors.
Cite this review
Pith. "Pith review of Three Combinatorial Algorithms for the Cave Polynomial of a Polymatroid." pith.science (2026). https://pith.science/paper/C5ZEHJOM
@misc{pith2026260107697,
author = {Pith},
title = {Pith review of: Three Combinatorial Algorithms for the Cave Polynomial of a Polymatroid},
year = {2026},
howpublished = {\url{https://pith.science/paper/C5ZEHJOM}},
note = {Machine review of arXiv:2601.07697}
}
read the original abstract
The cave polynomial of a polymatroid was recently introduced and used to study the syzygies of polymatroidal ideals. We study the combinatorial relationships between three formulas for the cave polynomial. As an application, we interpret the Snapper polynomial in terms of these three formulas.
Reference graph
Works this paper leans on
-
[1]
Math., vol
Michel Brion, Multiplicity-free subvarieties of flag varieties, Commutative algebra ( G renoble/ L yon, 2001), Contemp. Math., vol. 331, Amer. Math. Soc., Providence, RI, 2003, pp. 13--23. 2011763
2001
-
[2]
Federico Castillo, Yairon Cid-Ruiz, Fatemeh Mohammadi, and Jonathan Monta \ n o, K-polynomials of multiplicity-free varieties, arXiv preprint arXiv:2212.13091 (2022)
arXiv 2022
-
[3]
Yairon Cid-Ruiz , Jacob P. Matherne , and Anna Shapiro , Syzygies of polymatroidal ideals , arXiv e-prints (2025), arXiv:2507.13153
arXiv 2025
-
[4]
Tsakiris, Resolution of ideals associated to subspace arrangements, Algebra Number Theory 16 (2022), no
Aldo Conca and Manolis C. Tsakiris, Resolution of ideals associated to subspace arrangements, Algebra Number Theory 16 (2022), no. 5, 1121--1140. 4471038
2022
-
[5]
Christopher Eur and Matt Larson, K-theoretic positivity for matroids, arXiv preprint arXiv:2311.11996 (2023), to appear in Journal of Algebraic Geometry
arXiv 2023
-
[6]
Algebraic Combin
J\"urgen Herzog and Takayuki Hibi, Discrete polymatroids, J. Algebraic Combin. 16 (2002), no. 3, 239--268. 1957102
2002
-
[7]
Allen Knutson, Frobenius splitting, point-counting, and degeneration, arXiv preprint arXiv:0911.4941 (2009)
arXiv 2009
-
[8]
Matt Larson, Shiyue Li, Sam Payne, and Nicholas Proudfoot, K-rings of wonderful varieties and matroids, Advances in Mathematics 441 (2024), 109554
2024
Show all 9 references
-
[9]
P olyhedra and efficiency
Alexander Schrijver, Combinatorial optimization. P olyhedra and efficiency. V ol. B , Algorithms and Combinatorics, vol. 24,B, Springer-Verlag, Berlin, 2003, Matroids, trees, stable sets, Chapters 39--69. 1956925
2003
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.