REVIEW 4 major objections 5 minor 1 cited by
The Polymatroid Representation of a Greedoid, and Associated Galois Connections
T0 review · 4 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read The paper claims a normal greedoid is a polymatroid greedoid exactly when it is an optimistic interval greedoid whose kernels are closed under intersection, while flagging a critical error in the proof as currently written.
desk verdict The paper introduces a promising new framework for polymatroid greedoids but explicitly admits the main proof is broken, so the central theorem is unsupported as written. 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 construction is the greatest representation $\rho^\natural(X) = \min\{r(F) : F \text{ flat}, \kappa(F) \supseteq X\}$, the minimum rank of a flat whose kernel contains $X$. The paper tries to show that $\rho^\natural$ is a submodular polymatroid rank function and that $\sigma_{\rho^\natural} \circ \kappa$ and $\kappa^{-1}$ form a Galois insertion between the greedoid's flat lattice and the representation's closed-set lattice; this is what makes interval plus optimism plus kernel intersection sufficient. Optimism says every non-loop letter is a continuation at some prefix of every basic word, generalizing monotonicity of matroid span. The Forking Lemma (Lemma 4.1) is a new technical tool identifying that certain continuations of a meet of flats must be continuations of one of the flats, giving concrete witnesses for exchange arguments.
What would settle it
A single finite counterexample—a normal greedoid that is interval, optimistic, and satisfies Eq. (11) yet admits no polymatroid rank function satisfying Eq. (2)—would refute Theorem 6.2. A direct computational check is to form $\rho^\natural$ by Eq. (10) and test the diminishing-returns inequality $(\rho^\natural/X)(z) \geq (\rho^\natural/Y)(z)$ for all $X \subseteq Y$ and $z \notin Y$; a violation disproves Lemma 6.1 and the sufficiency direction.
Extended reading notes
Core claim
The main result (Theorem 6.2) asserts that for a normal greedoid, possession of an aligned polymatroid representation is equivalent to the conjunction of three combinatorial properties: the interval property, optimism, and kernel closure under intersection, written $\kappa(F \sqcap F') = \kappa(F) \cap \kappa(F')$ for all flats $F, F'$. The paper further claims (Corollary 6.3) that this is equivalent to the existence of an integral representation, and to the lattice of greedoid flats being isomorphic to the closed-set lattice of some polymatroid. Along the way it proves that aligned representations are exactly those giving a covering-preserving Galois connection between these two lattices. The authors state that the proof of the main result currently contains a critical error and that they are revising the claim and proof.
Load-bearing premise
The load-bearing premise is Lemma 6.1, which asserts that the greatest representation $\rho^\natural$ is a submodular polymatroid rank function whose adjoints form a Galois insertion; the manuscript states the proof of the main result currently has a critical error, so the sufficiency direction collapses if this lemma fails.
Editorial extensions
If this is right
- If Theorem 6.2 is correct, polymatroid greedoids are exactly the optimistic interval greedoids with kernels closed under intersection, a finite list of combinatorial conditions.
- Every polymatroid greedoid would then have an integral representation, so the continuous representations introduced here coincide existentially with the integral representations of [KL85a].
- The lattice of flats of a polymatroid greedoid would be isomorphic to the closed-set lattice of a polymatroid, making the greedoid's order structure tied to submodularity.
- The Galois-connection formulation would allow representation theory of greedoids to be studied through lattice duality rather than through explicit rank functions.
- This would settle the open characterization problem for polymatroid greedoids raised in [KL85a].
Reading between the lines
- If the proof can be repaired, the three conditions give a finite, checkable certificate for polymatroid greedoids, which could be turned into an algorithm that decides membership for a greedoid given by a finite language.
- The Galois-insertion view suggests the real content of 'being a polymatroid greedoid' is order-theoretic: the flat lattice embeds as a sublattice of a polymatroid closed-set lattice, which may open routes to characterizing larger greedy-algorithm classes by similar adjunctions.
- In the meantime, the explicit error note implies the theorem should not be used as a black box; the concrete object to examine is whether $\rho^\natural$ is submodular under the stated hypothesis.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies polymatroid greedoids, aiming to characterize them by the interval property, a new optimism condition, and intersection-closed kernels. The main theorem (Theorem 6.2) claims this is a necessary and sufficient condition, resolving an open question of Korte and Lovász. The approach introduces a canonical rank function ρ♮, constructs a Galois insertion between the greedoid flats and the closed sets of this representation, and derives several equivalent descriptions of polymatroid greedoids. The manuscript itself states, in the abstract and introduction, that there is a critical error in the proof of the main result and that the authors are revising the main claim and proof.
Significance. If correct, the main theorem would be the first purely combinatorial characterization of polymatroid greedoids and would resolve a long-standing open question. The paper also introduces potentially useful technical tools: the Forking Lemma and the notion of optimism, as well as a conceptually attractive Galois-connection framework for polymatroid representations. The auxiliary results on aligned representations (Lemma 5.6, Proposition 5.8, Corollaries 5.11–5.13) are of independent interest. However, because the central proof is acknowledged by the authors to contain a critical error, and because further load-bearing gaps remain in the arguments as written, the current version does not provide a proof of the advertised results.
major comments (4)
- [Abstract and §1] The manuscript explicitly declares: 'In this version of the manuscript, there is a critical error in the proof of the main result. The authors are currently revising the main claim and proof to resolve this discrepancy.' Since the error is not located or corrected anywhere in the text, Theorem 6.2 and its supporting Lemma 6.1 cannot be regarded as proved. The sufficiency direction of Theorem 6.2 is exactly the content of Lemma 6.1, so this is a load-bearing failure, not a presentational issue.
- [Lemma 6.1] In the submodularity proof of Lemma 6.1, the identity F_{Y+z} = F_Y ⊔ F_{X+z} is asserted without proof and is then combined with the semimodular submodular law to obtain the diminishing-returns inequality. This identity is the crucial step: without it, ρ♮ is not shown to be a polymatroid rank function, and the representation claim in Theorem 6.2 has no basis. The uniqueness argument preceding it also depends essentially on Eq. (11), so the proof cannot be repaired by a local rewording; it requires a proof of this lattice identity.
- [Corollary 6.3] The implication 4 ⇒ 5 uses the equality σρ(X ∩ Y) = σρ(X) ⊓ σρ(Y) for the span operator of a polymatroid. This equality is not valid for a general closure operator: σρ(X ∩ Y) is a closed set contained in σρ(X) ∩ σρ(Y), but it need not equal the intersection. Therefore the displayed submodularity verification for g ◦ σρ is not established. In addition, the isomorphism in item 4 is not specified, so the assertion that g ◦ σρ(α) = |α| for all feasible α does not follow from the stated assumptions.
- [Theorem 5.14] In the second direction of Theorem 5.14, the case analysis relies on a claim that certain assumptions make 'the first item cannot become true' at successive steps, and Eq. (9) asserts a strict chain of spans based on 0 < (ρ/α)(y) < 1. The strictness of the inclusion σρ(α + y) ⊂ σρ(α ∪ {x, y}) is not justified, since y may already lie in σρ(α + x). This weakens the proof of the Galois-connection characterization, which is advertised as a main contribution of the paper.
minor comments (5)
- [Title] The title contains a spacing typo: 'Associat ed' should read 'Associated'.
- [§3.3] The sentence 'the α→ relation disambiguate the order of letters' has a subject-verb agreement error; it should be 'disambiguates'.
- [Lemma 5.6] The proof uses the notation (f/α)(y) while the definition and surrounding text use ρ/α; the notation should be made consistent.
- [Appendix A] The verification of the antimatroid in Proposition A.2 is very terse; a direct check of the exchange axiom for the language A would improve readability.
- [Figure 4] The caption says 'This is not an insertion since ϕ∗ ◦ ϕ∗({b}) = ∅', but {b} appears to be an element of Lρ; the intended statement and the elements of Lρ should be clarified.
Circularity Check
No circular reasoning found; the acknowledged critical error is a correctness defect, not a self-referential derivation.
full rationale
Walking the claimed derivation chain, I find no step in which an output is equivalent to an input by construction, no fitted parameter renamed as a prediction, and no load-bearing self-citation chain. The central construction is the greatest representation rho^natural defined in Eq. 10 from the greedoid's flats and kernels; Lemma 6.1 then proves, rather than assumes, that rho^natural is a submodular polymatroid rank function and a representation. The sufficiency direction of Theorem 6.2 uses Lemma 6.1, and the necessity direction uses Lemmas 5.6, 5.10, and 5.12, all of which are proven from the definition of aligned representation and standard submodularity. The property Eq. 11 appears both as an assumption of Lemma 6.1 and as a condition in Theorem 6.2, but that is exactly the biconditional statement being proved, not a circular reduction. The only self-citation is Garg's lattice-theory textbook [Gar15], used as background reference in the preliminaries; it is not load-bearing for the main theorem. The external citations to Korte--Lovasz [KL85a], Birkhoff [Bir35], and Edmonds [Edm03] are legitimate prior results used as tools. The manuscript's explicit admission, 'In this version of the manuscript, there is a critical error in the proof of the main result. The authors are currently revising the main claim and proof to resolve this discrepancy,' is a serious correctness and verifiability problem for the current version, but it is not circularity: an erroneous or unsupported proof is not the same as a derivation that reduces to its own inputs. Accordingly, no specific circular step can be exhibited with the required exact-quote reduction, so the circularity score is 0.
Assumptions & free parameters
assumptions (4)
- standard math Finite ground set and simple language for greedoids.
- domain assumption Normality: the greedoid has no loops.
- standard math The lattice of flats of an interval greedoid is semimodular.
- standard math Birkhoff-Edmonds result that closed sets of a polymatroid form a lattice under intersection.
Cite this review
Pith. "Pith review of The Polymatroid Representation of a Greedoid, and Associated Galois Connections." pith.science (2026). https://pith.science/paper/LY2TFOK5
@misc{pith2026241115363,
author = {Pith},
title = {Pith review of: The Polymatroid Representation of a Greedoid, and Associated Galois Connections},
year = {2026},
howpublished = {\url{https://pith.science/paper/LY2TFOK5}},
note = {Machine review of arXiv:2411.15363}
}
read the original abstract
A greedoid is a generalization of a matroid allowing for more flexible analyses and modeling of combinatorial optimization problems. However, these structures decimate many matroid properties contributing to their pervasive nature. A polymatroid greedoid [KL85] presents an interesting middle ground, so we further develop this class. First we prove every local poset greedoid for which the greedy algorithm correctly solves linear optimizations over its basic words must have a polymatroid representation. For this, we use relationships between the lattices of greedoid flats and closed sets of a polymatroid to generalize concepts in [KL85]. Then, we show our generalization is defined by a Galois connection between the greedoid flats and closed sets of a representation. Finally, we apply this duality to identify a subclass of polymatroid greedoids with favorable properties, which we call strong polymatroid greedoids. As technical tools for our analyses, we introduce optimism and the Forking Lemma for interval greedoids. Both are pervasive in our work, and are of independent interest.
Figures
Figures from the paper (1 more)
Forward citations
Cited by 1 Pith paper
-
Approximation Algorithms for Matroidal Prerequisite Systems
MPS admit efficient Δ- and (1+λ_max)-approximations for additive maximization and (2+λ_max) / Δ^{2}(1-1/e-δ)^{-1} approximations for monotone submodular maximization, with Gap-ETH hardness ruling out min{Δ,λ_max}^{o(1)}.
Reference graph
Works this paper leans on
-
[1]
The antimatroid is an optimistic greedoid which is not gua ranteed to possess the interval property,
-
[2]
First we must define an antimatroid: Let A be a greedoid
The trimmed matroid is an interval greedoid which is not gu aranteed to be optimistic. First we must define an antimatroid: Let A be a greedoid. Then, A is an antimatroid if and only if, it is normal and for all feasible α, β ∈ A, ˜α ⁄⊆˜β =⇒ (∃x ∈ ˜α) βx ∈ A. (14) The reader should note that this is equivalent to saying that the subsets of the alphabet whi...
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.