REVIEW 5 minor 12 references
Decomposable polymatroids and connections with graph coloring
T0 review · 0 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Every 2-polymatroid counts like a graph's colorings. The paper proves that the chromatic polynomial of any rank-at-most-two polymatroid is a rational multiple of the chromatic polynomial of some graph, so the number of matroid…
desk verdict The paper's decomposition-counting chromatic polynomial is a real new invariant, and the 2-polymatroid rational-multiple theorem holds up given Lemos's classification—worthy of a serious referee. 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 load-bearing mechanism is the incidence set: a subset $X$ of size at least two for which $\rho(Y)=1+\sum_{e\in Y}(\rho(e)-1)$ for every small $Y\subseteq X$. Lemma 2.2 shows that in any decomposition the elements of an incidence set must be parallel in exactly one matroid and in no other, which is what lets decompositions be read as colorings of the hypergraph's line graph. For Theorem 3.1 the central device is the mixing graph associated with a pair of matroids whose rank functions sum to the polymatroid: its vertices are the subsets where the two ranks differ, its edges join comparable sets or nearly disjoint sets, and the connected components of this graph parameterize all alternative decompositions of the same rank-function sum. A new lemma proves that when one of the two matroids is connected and the other has exactly two components, this mixing graph has at most two components, so the number of decompositions is small enough to be summed explicitly. For the quotient-polymatroid section, recurrence (5.2) reconstructs the unique quotient-chain decomposition directly from the polymatroid rank function, and the excluded minors are two-element polymatroids $\rho_A$ indexed by three-element sets of nonnegative integers.
What would settle it
Compute the chromatic polynomial of every 2-polymatroid on, say, up to six elements by exhaustive enumeration of their decompositions; if any resulting polynomial is not of the form $s\cdot\chi(G;x)$ for a rational $s$ and some graph $G$, Theorem 3.1 fails. Conversely, an independent re-derivation of the quoted classification of decompositions of connected 2-polymatroids, tested on small ground sets, would either confirm the missing-case-free status of the proof or expose a counterexample to it.
Extended reading notes
Core claim
The central discovery is Theorem 3.1: if $\rho$ is any 2-polymatroid, then $\chi(\rho;x)=s\cdot\chi(G;x)$ for some graph $G$ and rational $s$, where $\chi(\rho;k)$ counts ordered $k$-tuples of matroids whose rank functions sum to $\rho$. The proof reduces to connected 2-polymatroids and splits them by a prior classification of their decompositions: when all decompositions are equivalent the polynomial is a chromatic polynomial divided by factorial multiplicities of repeated matroids; when some pair of decompositions is non-preserving the decompositions are exactly two 2-sum families and the polynomial is $x(x-1)^2$; when decompositions are inequivalent but preserving they contain either two matroids or a connected matroid plus one with two connected components, the last case being settled by proving that the associated mixing graph has at most two components, giving $\chi(\rho;x)=x^2(x-1)$. The accompanying hypergraph theorem shows that, under conditions (H2), (H3), and (T), the polymatroids built from equation (2.1) have $k$-decompositions in bijection with $k$-colorings of the line graph, and the quotient-polymatroid results give exact excluded-minor lists.
Load-bearing premise
The theorem that every 2-polymatroid's chromatic polynomial is a rational multiple of a graph's chromatic polynomial assumes without independent proof that the published classification of decompositions of connected 2-polymatroids, quoted as three theorems, is complete and correct; a missing case in that classification would leave a 2-polymatroid whose polynomial is not graph-like.
Editorial extensions
If this is right
- For every 2-polymatroid, the number of ordered $k$-matroid decompositions is a polynomial in $k$, and up to a rational factor it is exactly the number of proper $k$-colorings of some graph.
- The hypergraph construction produces excluded minors for the decomposable classes $D_k$ corresponding to $(k+1)$-critical graphs, so finding all excluded minors for $D_k$ is at least as hard as classifying all critical graphs; affine and projective planes show the chromatic gap after deleting or contracting one element can be arbitrarily large.
- Under mild rank conditions, a polymatroid and its $i$-dual have the same chromatic polynomial, so decomposition counts are invariant under dualization in those cases.
- The class of $k$-quotient polymatroids has exactly $\binom{k+1}{3}$ excluded minors, all on two elements, and the union over all $k$ has one excluded minor for every three-element set of nonnegative integers.
- A 2-quotient polymatroid has rank difference between its two matroids at most $t$ if and only if it has no $U_{t+1,t+1}$ minor.
Reading between the lines
- If Theorem 3.1 is right, the mixing-graph component count is the true invariant controlling 2-polymatroid decomposition counts; the same device could classify decomposition-count polynomials for sums of two matroids of any rank, suggesting a decomposition-count analogue of the Tutte polynomial.
- The abundance of excluded minors for $D_k$ means an excluded-minor characterization of decomposable polymatroids is probably hopeless; the chromatic-polynomial formulation gives a more tractable invariant, and the hypergraph construction shows that this invariant can realize arbitrary graph coloring data.
- One testable extension: enumerate all 2-polymatroids on small ground sets, compute their chromatic polynomials, and check not only the rational-multiple form but whether the graph $G$ and rational $s$ can be chosen canonically, for instance from the components of the mixing graph.
- The quotient-polymatroid excluded-minor list is so concrete that it invites checking whether similar two-element excluded minors characterize other minor-closed polymatroid classes defined by inequalities between matroid rank functions.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies decomposable integer polymatroids, i.e., polymatroids expressible as sums of matroid rank functions. It introduces chromatic numbers and chromatic polynomials for polymatroids by counting ordered decompositions into matroid rank sums. Theorem 2.3 constructs, from hypergraphs satisfying conditions (H2), (H3), and (T), polymatroids whose ordered k-decompositions are in bijection with k-colorings of the line graph of the hypergraph, yielding exact chromatic polynomials, new excluded minors for the classes D_k, and indecomposability criteria for truncations. The paper's main structural result, Theorem 3.1, asserts that the chromatic polynomial of every 2-polymatroid is a rational multiple of the chromatic polynomial of some graph. Section 4 develops dualities and shows when a polymatroid and its i-dual have equal chromatic polynomials, and Section 5 determines the excluded minors for the minor-closed class of k-quotient polymatroids.
Significance. If correct, Theorem 3.1 is a surprising and valuable bridge: for rank at most two, the function counting matroid decompositions is always a graph coloring count up to rational scaling, while Example 8 shows that this fails for rank-three polymatroids. The hypergraph construction in Section 2 is elegant and produces abundant excluded minors, connecting decomposability to graph criticality. The paper is careful with its local arguments, and I found no internal inconsistency. The proof of Theorem 3.1 explicitly imports deep classification theorems of Lemos and Lemos-Mota; this is acceptable practice because the statements are quoted precisely, but it means the central theorem inherits its risk from those external results. The paper also gives explicit finite excluded-minor sets for quotient polymatroids, which is a clean and checkable contribution.
minor comments (5)
- [Section 3, after Theorem 3.4] The case split for inequivalent decompositions should state explicitly that a two-matroid decomposition in which both matroids are disconnected falls under option (1) and is therefore already covered by the x(x-1) rational-multiple argument; as written, the reader may misread the split as assuming at least one of the two matroids is connected.
- [Section 3, Example 8] The displayed computation writes 'χ(ρ;k) = (x)_6 + ... = x^6 - ...'; since the right-hand side is a polynomial in x, this should read 'χ(ρ;x)'.
- [Section 3, proof of Theorem 3.1] It would improve audibility to add one sentence identifying which quoted result (Theorem 3.3 or Lemos-Mota's reconstruction theorem) rules out the remaining configuration of a decomposition with two disconnected matroids and no equivalent connected/two-component decomposition, rather than leaving the exhaustiveness entirely implicit.
- [Section 2, Corollary 2.7] The step 'χ(ρ\e) ≤ χ(G_e)' uses Lemma 2.4 applied to the hypergraph with hyperedges X_i - {e}; this is correct, but the line graph of that hypergraph is a subgraph of G_e, and saying so explicitly would make the inequality immediate.
- [Throughout] The present text contains numerous spacing and font artifacts (for example, 'POL YMA TROIDS' in the title, 'Carol yn Chun', and 'Definition'); these should be cleaned in the final version, presumably by recompiling from the original source.
Circularity Check
No circularity: central equalities are proved bijections; external Lemos classification is independent support, not a self-citation chain.
full rationale
The paper's derivation chain does not reduce any claimed result to its own inputs. Definition 1.1 defines the polymatroid chromatic polynomial by counting ordered decompositions, while Theorem 2.3 independently proves a bijection between k-colorings of the line graph of a hypergraph and ordered k-decompositions of the constructed polymatroid; this is a substantive combinatorial argument, not an identity forced by definition. Theorem 3.1, the rational-multiple result for 2-polymatroids, is obtained by splitting connected 2-polymatroids into cases controlled by classification theorems of Lemos and Lemos–Mota. Those theorems are quoted from external prior work, not from the present authors, and they do not assume the target statement; reliance on them creates verification risk if a classification case were missing, but that is a correctness concern, not circularity. No fitted parameters are called predictions, no normalization is chosen to force the graph-chromatic-polynomial form, and no load-bearing premise is justified by self-citation. The absence of reproduced proofs for the external classification theorems affects the paper's independence from unexamined assumptions, but it does not make the derivation circular.
Assumptions & free parameters
assumptions (5)
- standard math Lemos's classification of non-preserving pairs of decompositions of connected 2-polymatroids (Theorem 3.2, from [7]).
- standard math Lemos's reduction theorems for preserving inequivalent decompositions (Theorems 3.3 and 3.4, from [7]).
- standard math Lemos-Mota theorem that every pair of matroids with equal rank sum arises from the mixing graph G_{M1,M2} (Lemma 3.1 and Theorem 4.1, from [8]).
- standard math Standard matroid facts from Oxley: minors, duality, parallel classes, circuits, and quotient definitions.
- standard math Brylawski's quotient characterization: Q is a quotient of L iff the rank difference rL - rQ is non-decreasing (Lemma 5.1, from [1]).
Cite this review
Pith. "Pith review of Decomposable polymatroids and connections with graph coloring." pith.science (2026). https://pith.science/paper/XGM26TXQ
@misc{pith2026190809030,
author = {Pith},
title = {Pith review of: Decomposable polymatroids and connections with graph coloring},
year = {2026},
howpublished = {\url{https://pith.science/paper/XGM26TXQ}},
note = {Machine review of arXiv:1908.09030}
}
read the original abstract
We introduce ideas that complement the many known connections between polymatroids and graph coloring. Given a hypergraph that satisfies certain conditions, we construct polymatroids, given as rank functions, that can be written as sums of rank functions of matroids, and for which the minimum number of matroids required in such sums is the chromatic number of the line graph of the hypergraph. This result motivates introducing chromatic numbers and chromatic polynomials for polymatroids. We show that the chromatic polynomial of any 2-polymatroid is a rational multiple of the chromatic polynomial of some graph. We also find the excluded minors for the minor-closed class of polymatroids that can be written as sums of rank functions of matroids that form a chain of quotients.
Reference graph
Works this paper leans on
-
[1]
Brylawski, Constructions, in: Theory of Matroids, N
T.H. Brylawski, Constructions, in: Theory of Matroids, N. White ed. (Cambridge Univ. Press, Cambridge,
-
[2]
Chun, Deletion-contraction to form a polymatroid, Discrete Math
D. Chun, Deletion-contraction to form a polymatroid, Discrete Math. 309 (2009) 2592–2595
work page 2009
-
[3]
J. Geelen and G. Whittle, Branch-width and Rota’s conjec ture, J. Combin. Theory Ser . B86 (2002) 315–330
work page 2002
-
[4]
T. Helgason, Aspects of the theory of hypermatroids, in: Hypergraph Seminar (Lecture Notes in Math., V ol. 411, Springer, Berlin, 1974) 191–213
work page 1974
-
[5]
J. Herzog and T. Hibi, Discrete polymatroids, J. Algebraic Combin. 16 (2002) 239–268
work page 2002
-
[6]
Lemos, On the connectivity function of a binary matroi d, J
M. Lemos, On the connectivity function of a binary matroi d, J. Combin. Theory Ser . B 86 (2002) 114–132
work page 2002
-
[7]
Lemos, Uniqueness of the decomposition of the rank fun ction of a 2-polymatroid, Discrete Math
M. Lemos, Uniqueness of the decomposition of the rank fun ction of a 2-polymatroid, Discrete Math. 269 (2003) 161–179. DECOMPOSABLE POLYMA TROIDS 21
work page 2003
-
[8]
M. Lemos and S. Mota, The reconstruction of a matroid from its connectivity function, Discrete Math. 220 (2000) 131–143
work page 2000
Show all 12 references
-
[9]
Mat´ uˇ s, Excluded minors for Boolean polymatroids,Discrete Math
F. Mat´ uˇ s, Excluded minors for Boolean polymatroids,Discrete Math. 235 (2001) 317–321
2001
-
[10]
Murty and I
U.S.R. Murty and I. Simon, A β -function that is not a sum of rank functions of matroids, in: Probl` emes combinatoires et th´ eorie des graphes (Colloq. Internat. C NRS, Univ. Orsay, Orsay, 1976) , (CNRS, Paris,
1976
-
[11]
Oxley, Matroid Theory, second edition (Oxford University Press, Oxford, 2011)
J. Oxley, Matroid Theory, second edition (Oxford University Press, Oxford, 2011)
2011
-
[12]
Oxley and G
J. Oxley and G. Whittle, Some excluded-minor theorems f or a class of polymatroids, Combinatorica 13 (1993) 467–476. (J. Bonin) D EPARTMENT OF MATHEMATICS , T HE GEORGE WASHINGTON UNIVERSITY , WASHINGTON , D.C. 20052, USA E-mail address, J. Bonin: jbonin@gwu.edu (C. Chun) D EP...
1993
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.