# Polymatroid

A **polymatroid** is a combinatorial structure defined either as a polytope or, equivalently, as a finite ground set equipped with a rank function that is monotone and submodular and vanishes on the empty set. The concept was introduced by [Jack Edmonds](https://www.edgepedia.org/jack-edmonds), a combinatorial optimization researcher then at the National Bureau of Standards, in his 1970 paper "Submodular functions, matroids, and certain polyhedra" as a generalization of the matroid<sup>[1](https://people.ece.uw.edu/bilmes/classes/ee563/ee563_spring_2014/lecture16_presented.pdf)</sup>. Polymatroids sit at the intersection of submodular function theory, polyhedral combinatorics, information theory, and matroid theory.

| Key fact | Detail |
|---|---|
| Rank function axioms | A function \( f : 2^S \to \mathbf{R} \) is a polymatroid rank function if it is monotone (\( A \subseteq B \) implies \( f(A) \le f(B) \)), submodular, and satisfies \( f(\emptyset) = 0 \)<sup>[2](https://repository.dl.itc.u-tokyo.ac.jp/record/51069/files/A34098.pdf)</sup> |
| Polytope form | The associated polytope is \( P(f) = \{ x \in \mathbf{R}^S_+ : x(A) \le f(A) \text{ for all } A \subseteq S \} \); Edmonds originally defined the polymatroid to be this polytope<sup>[3](https://webspace.maths.qmul.ac.uk/a.fink/matroid_subdivisions_Edmonds2015.pdf)</sup> |
| Relation to matroids | If \( f \) is integer-valued and \( f(x) \le 1 \) for every single element \( x \), the polymatroid is a matroid<sup>[4](https://doi.org/10.1016%2Fj.dam.2025.06.028)</sup> |
| Greedy optimization | Edmonds (1970) proved the greedy algorithm maximizes any linear function \( w^{\top} x \) over \( P(f) \) if and only if \( f \) is normalized, non-decreasing, and submodular<sup>[5](https://digital.lib.washington.edu/researchworks/bitstreams/b0051e15-a566-488b-83e6-9e4471e542af/download)</sup> |
| Information theory | The entropy function of a collection of random variables, viewed as a set function, is a polymatroid rank function (Fujishige, 1978)<sup>[6](https://faculty.coe.drexel.edu/jwalsh/Congduan_allerton13.pdf)</sup> |
| Linear representation | A polymatroid is \( K \)-linearly representable if \( f(X) = \dim \sum_{x \in X} V_x \) for a collection of subspaces of a \( K \)-vector space<sup>[7](https://web.mat.upc.edu/carles.padro/arc02v03.pdf)</sup> |

## Definition

Let \( S \) be a finite set. A function \( f : 2^S \to \mathbf{R} \) is called a *polymatroid rank function* if it satisfies three conditions: normalization, \( f(\emptyset) = 0 \); monotonicity, \( A \subseteq B \) implies \( f(A) \le f(B) \); and the submodular inequality, \( f(A) + f(B) \ge f(A \cap B) + f(A \cup B) \) for all \( A, B \subseteq S \)<sup>[2](https://repository.dl.itc.u-tokyo.ac.jp/record/51069/files/A34098.pdf)</sup><sup> • </sup><sup>[3](https://webspace.maths.qmul.ac.uk/a.fink/matroid_subdivisions_Edmonds2015.pdf)</sup>. The pair \( (S, f) \) is then a polymatroid, and \( f \) is its rank function<sup>[2](https://repository.dl.itc.u-tokyo.ac.jp/record/51069/files/A34098.pdf)</sup>.

The submodularity condition can be checked locally: a function \( \mathrm{rk} \) with \( \mathrm{rk}(\emptyset) = 0 \) satisfying \( \mathrm{rk}(S \cup \{a\}) + \mathrm{rk}(S \cup \{b\}) \ge \mathrm{rk}(S) + \mathrm{rk}(S \cup \{a, b\}) \) for all \( S \subseteq E \) and \( a, b \notin S \) is already a polymatroid rank function<sup>[3](https://webspace.maths.qmul.ac.uk/a.fink/matroid_subdivisions_Edmonds2015.pdf)</sup>.

## The polytope viewpoint

Edmonds defined the polymatroid itself as the *independence polytope*

\[ P_{\mathrm{ind}}(\mathrm{rk}) = \left\{ x \in \mathbf{R}^E_+ : \sum_{i \in A} x_i \le \mathrm{rk}(A) \text{ for all } A \subseteq E \right\}, \]

together with the *base polytope*, which adds the equality \( \sum_{i \in E} x_i = \mathrm{rk}(E) \)<sup>[3](https://webspace.maths.qmul.ac.uk/a.fink/matroid_subdivisions_Edmonds2015.pdf)</sup>. The correspondence goes both ways: for a polymatroid \( P \), the function \( f(A) = \max\{ x(A) : x \in P \} \) is the unique polymatroid rank function with \( P = P_+(f) \), so every polymatroid polytope determines its defining function<sup>[2](https://repository.dl.itc.u-tokyo.ac.jp/record/51069/files/A34098.pdf)</sup>.

The vertices of these polytopes have an explicit description. For a submodular \( f \) with \( f(\emptyset) = 0 \), the vertices of the extended polymatroid are obtained by ordering the ground set in every possible permutation \( \pi \) and setting \( x(s_{\pi(i)}) = f(\{s_{\pi(1)}, \ldots, s_{\pi(i)}\}) - f(\{s_{\pi(1)}, \ldots, s_{\pi(i-1)}\}) \)<sup>[8](https://page.math.tu-berlin.de/~felsner/Lehre/SemMatS/Literatur/Schrijver-44%3ASubmod%2BPolymat.pdf)</sup>. When \( f \) is a matroid rank function, every vertex of the independence or base polytope has all coordinates equal to 0 or 1<sup>[3](https://webspace.maths.qmul.ac.uk/a.fink/matroid_subdivisions_Edmonds2015.pdf)</sup>.

Some later authors use a slightly more general notion than Edmonds' original one, since Edmonds' polymatroids lie in the positive orthant \( \mathbf{R}^n_{\ge 0} \)<sup>[9](https://people.brandeis.edu/~bernardi/publications/TuttePolymatroids-v6.pdf)</sup>.

## Relation to matroids

A matroid is the special case of a polymatroid in which the rank function is integer-valued and \( f(x) \le 1 \) for every element \( x \)<sup>[4](https://doi.org/10.1016%2Fj.dam.2025.06.028)</sup>. In that case a \( K \)-linear representation by subspaces can be replaced by a representation by vectors, since each subspace has dimension at most 1<sup>[4](https://doi.org/10.1016%2Fj.dam.2025.06.028)</sup>. Conversely, every integer polymatroid can be derived from a matroid, by a construction of Helgason (1974) that replaces each element \( s \) by a set \( X_s \) of size \( f(\{s\}) \)<sup>[8](https://page.math.tu-berlin.de/~felsner/Lehre/SemMatS/Literatur/Schrijver-44%3ASubmod%2BPolymat.pdf)</sup>.

Polymatroids inherit matroid-style operations. For a polymatroid \( S = (Q, f) \) and \( Z \subseteq Q \), the deletion and contraction are \( S \setminus Z = (Q - Z, f_{\setminus Z}) \) with \( f_{\setminus Z}(A) = f(A) \), and \( S / Z = (Q - Z, f_{/Z}) \) with \( f_{/Z}(A) = f(A \cup Z) - f(Z) \); anything obtained by repeated application is a minor, and the minors of a matroid are matroids<sup>[7](https://web.mat.upc.edu/carles.padro/arc02v03.pdf)</sup>.

## Optimization and the greedy algorithm

The algorithmic importance of polymatroids comes from a characterization by Edmonds. Given a polytope \( P_f = \{ x \in \mathbf{R}^{\lvert V \rvert}_+ : x(Y) \le f(Y) \text{ for all } Y \subseteq V \} \), the greedy algorithm, which sorts elements by decreasing weight \( w \) and sets \( x(i) = f(X_i) - f(X_{i-1}) \) along the sorted prefixes, solves \( \max_{x \in P_f} w^{\top} x \) for every \( w \) if and only if \( f \) is normalized, non-decreasing, and submodular<sup>[5](https://digital.lib.washington.edu/researchworks/bitstreams/b0051e15-a566-488b-83e6-9e4471e542af/download)</sup>. Geometrically, the greedy method walks from the origin along the edges of the polytope, first as far as possible in the direction of the highest-weight element, then in the direction of the next, and so on, reaching an optimal vertex<sup>[8](https://page.math.tu-berlin.de/~felsner/Lehre/SemMatS/Literatur/Schrijver-44%3ASubmod%2BPolymat.pdf)</sup>. With \( f \) given by a value-giving oracle, the optimum can be found in strongly polynomial time<sup>[8](https://page.math.tu-berlin.de/~felsner/Lehre/SemMatS/Literatur/Schrijver-44%3ASubmod%2BPolymat.pdf)</sup>.

Edmonds also proved an intersection theorem: for two submodular functions \( f, g : 2^E \to \mathbf{R}_+ \), the system \( \sum_{e \in A} x_e \le f(A) \), \( \sum_{e \in A} x_e \le g(A) \) for all \( A \subseteq E \), and \( x \ge 0 \) is totally dual integral, which yields a polyhedral description of matroid intersection as a corollary<sup>[10](https://www.or.uni-bonn.de/~held/combo/1415/lecturenotes/CombOpt.pdf)</sup>.

## Linear representability

A polymatroid \( (E, f) \) is *linearly representable* over a field \( K \) if there exists a collection \( (V_x)_{x \in E} \) of vector subspaces of a \( K \)-vector space \( V \) such that \( f(X) = \dim \sum_{x \in X} V_x \) for every \( X \subseteq E \)<sup>[4](https://doi.org/10.1016%2Fj.dam.2025.06.028)</sup>. For an integer polymatroid with ground set \( Q \), a tuple of subspaces \( (V_i)_{i \in Q} \) defines the rank function \( f(X) = \dim \sum_{i \in X} V_i \), and such polymatroids are called \( K \)-linearly representable<sup>[7](https://web.mat.upc.edu/carles.padro/arc02v03.pdf)</sup>. All minors of a \( K \)-linear integer polymatroid are again \( K \)-linear<sup>[7](https://web.mat.upc.edu/carles.padro/arc02v03.pdf)</sup>. Multiples of \( K \)-linear polymatroids are called \( K \)-poly-linear; a matroid \( (Q, r) \) is \( K \)-poly-linear if and only if \( (Q, c \cdot r) \) is \( K \)-linear for some positive integer \( c \)<sup>[7](https://web.mat.upc.edu/carles.padro/arc02v03.pdf)</sup>.

## Polymatroids in information theory

Entropy provides the leading example of a polymatroid rank function outside combinatorial optimization. Fujishige observed in 1978 that the entropy function \( H(X_A) \), evaluated on subsets \( A \) of a collection of random variables, is non-decreasing and submodular with \( H(\emptyset) = 0 \), hence a polymatroid rank function<sup>[6](https://faculty.coe.drexel.edu/jwalsh/Congduan_allerton13.pdf)</sup>. The set of all polymatroids of order \( n \), denoted \( \Gamma_n \), is called the polymatroidal region; since every entropy function is a polymatroid, \( \Gamma_n \) is an outer bound on the region of entropic vectors, and its bounding inequalities are exactly the Shannon-type information inequalities<sup>[11](https://pmc.ncbi.nlm.nih.gov/articles/PMC7999956/)</sup>. Not every polymatroid is entropic: on an extreme ray of \( \Gamma_3 \) generated by the uniform matroid \( U_{2,3} \), a vector \( c \cdot U_{2,3} \) is entropic if and only if \( c = \log v \) for some positive integer \( v \)<sup>[11](https://pmc.ncbi.nlm.nih.gov/articles/PMC7999956/)</sup>.

Polymatroidal structures also appear in network coding. Te Sun Han, an information theorist, showed in 1980 that reliable transmission of correlated multiple sources to a single sink admits a necessary and sufficient condition phrased in terms of polymatroidal functions, and his 2010 work unifies this with the 2000 max-flow min-cut theorem of Ahlswede, Cai, Li, and Yeung for network coding multicast, giving conditions for multicasting correlated sources over noisy networks<sup>[12](https://arxiv.org/abs/1004.1564)</sup>.

## q-Polymatroids and coding theory

A \( q \)-analog replaces subsets of a finite set by subspaces of a finite-dimensional vector space over a finite field. While \( \mathbb{F}_{q^m} \)-linear rank-metric codes give rise to \( q \)-matroids, \( \mathbb{F}_q \)-linear rank-metric codes induce \( q \)-polymatroids, in which the rank function attains rational values; this slight generality makes \( q \)-polymatroids much less rigid than \( q \)-matroids<sup>[13](https://arxiv.org/abs/2104.06570)</sup>. Deletion and contraction are dual operations on \( q \)-polymatroids, mirroring the puncturing and shortening of rank-metric codes, and the flats of the associated \( q \)-polymatroid completely determine a rank-metric code's generalized rank weights<sup>[13](https://arxiv.org/abs/2104.06570)</sup>.

## References

1. [Jack Edmonds (1970). Submodular Functions, Matroids, and Certain Polyhedra. Combinatorial Structures and Their Applications, pp. 69–87.](https://people.ece.uw.edu/bilmes/classes/ee563/ee563_spring_2014/lecture16_presented.pdf)
2. [Submodular Functions and Polymatroids (course notes, University of Tokyo repository)](https://repository.dl.itc.u-tokyo.ac.jp/record/51069/files/A34098.pdf)
3. [Alex Fink (2015). Polymatroid Subdivision, notes for Jack Edmonds' mini-course.](https://webspace.maths.qmul.ac.uk/a.fink/matroid_subdivisions_Edmonds2015.pdf)
4. [A note on extension properties and representations of matroids, Discrete Applied Mathematics (2025)](https://doi.org/10.1016%2Fj.dam.2025.06.028)
5. [Greedy algorithms for submodular optimization (thesis, Drexel University)](https://digital.lib.washington.edu/researchworks/bitstreams/b0051e15-a566-488b-83e6-9e4471e542af/download)
6. [Matroid Bounds on the Region of Entropic Vectors (Allerton conference paper)](https://faculty.coe.drexel.edu/jwalsh/Congduan_allerton13.pdf)
7. [Carles Padró. Linear Representations of Matroids and Polymatroids (course notes)](https://web.mat.upc.edu/carles.padro/arc02v03.pdf)
8. [Alexander Schrijver. Combinatorial Optimization, Chapter 44: Submodular functions and polymatroids](https://page.math.tu-berlin.de/~felsner/Lehre/SemMatS/Literatur/Schrijver-44%3ASubmod%2BPolymat.pdf)
9. [Olivier Bernardi, Tamás Kálmán, Alexander Postnikov. Universal Tutne polynomial for polymatroids](https://people.brandeis.edu/~bernardi/publications/TuttePolymatroids-v6.pdf)
10. [Stephan Held. Definitions & Theorems, Combinatorial Optimization 2014/15 (University of Bonn lecture notes)](https://www.or.uni-bonn.de/~held/combo/1415/lecturenotes/CombOpt.pdf)
11. [Matroidal Entropy Functions: A Quartet of Theories of Information, Matroid, Design, and Coding (Entropy/PMC)](https://pmc.ncbi.nlm.nih.gov/articles/PMC7999956/)
12. [Te Sun Han (2010). Polymatroids with Network Coding. arXiv:1004.1564](https://arxiv.org/abs/1004.1564)
13. [q-Polymatroids and Their Relation to Rank-Metric Codes. arXiv:2104.06570](https://arxiv.org/abs/2104.06570)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Matroid theory › Generalizations: polymatroids, delta-matroids, and beyond*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license