Encyclopedia

Polymatroid

Multiset analogue of matroids

Wikipedia contributorsAdapted for Fathomly · View authors

3 min read
Source updated May 11, 2026

In mathematics, a polymatroid is a polytope associated with a submodular function. The notion was introduced by Jack Edmonds in 1970. It is also a generalization of the notion of a matroid.

01Definition

Polyhedral definition

Let $E$ be a finite set and $f:2^{E}\rightarrow \mathbb {R} _{\geq 0}$ a non-decreasing submodular function, that is, for each $A\subseteq B\subseteq E$ we have $f(A)\leq f(B)$ , and for each $A,B\subseteq E$ we have $f(A)+f(B)\geq f(A\cup B)+f(A\cap B)$ . We define the polymatroid associated to $f$ to be the following polytope:

$P_{f}={\Big \{}{\textbf {x}}\in \mathbb {R} _{\geq 0}^{E}~{\Big |}~\sum _{e\in U}{\textbf {x}}(e)\leq f(U),\forall U\subseteq E{\Big \}}$ .

When we allow the entries of ${\textbf {x}}$ to be negative we denote this polytope by $EP_{f}$ , and call it the extended polymatroid associated to $f$ .

Matroidal definition

In matroid theory, polymatroids are defined as the pair consisting of the set and the function as in the above definition. That is, a polymatroid is a pair $(E,f)$ where $E$ is a finite set and $f:2^{E}\rightarrow \mathbb {R} _{\geq 0}$ , or $\mathbb {Z} _{\geq 0},$ is a non-decreasing submodular function. If the codomain is $\mathbb {Z} _{\geq 0},$ we say that $(E,f)$ is an integer polymatroid. We call $E$ the ground set and $f$ the rank function of the polymatroid. This definition generalizes the definition of a matroid in terms of its rank function. A vector $x\in \mathbb {R} _{\geq 0}^{E}$ is independent if $\sum _{e\in U}x(e)\leq f(U)$ for all $U\subseteq E$ . Let $P$ denote the set of independent vectors. Then $P$ is the polytope in the previous definition, called the independence polytope of the polymatroid.

Under this definition, a matroid is a special case of integer polymatroid. While the rank of an element in a matroid can be either $0$ or $1$ , the rank of an element in a polymatroid can be any nonnegative real number, or nonnegative integer in the case of an integer polymatroid. In this sense, a polymatroid can be considered a multiset analogue of a matroid.

Vector definition

Let $E$ be a finite set. If ${\textbf {u}},{\textbf {v}}\in \mathbb {R} ^{E}$ then we denote by $|{\textbf {u}}|$ the sum of the entries of ${\textbf {u}}$ , and write ${\textbf {u}}\leq {\textbf {v}}$ whenever ${\textbf {v}}(i)-{\textbf {u}}(i)\geq 0$ for every $i\in E$ (notice that this gives a partial order to $\mathbb {R} _{\geq 0}^{E}$ ). A polymatroid on the ground set $E$ is a nonempty compact subset $P$ , the set of independent vectors, of $\mathbb {R} _{\geq 0}^{E}$ such that:

If ${\textbf {v}}\in P$ , then ${\textbf {u}}\in P$ for every ${\textbf {u}}\leq {\textbf {v}}.$
If ${\textbf {u}},{\textbf {v}}\in P$ with $|{\textbf {v}}|>|{\textbf {u}}|$ , then there is a vector ${\textbf {w}}\in P$ such that ${\textbf {u}}<{\textbf {w}}\leq (\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {v}}({|E|})\}).$

This definition is equivalent to the one described before, where $f$ is the function defined by

$f(A)=\max {\Big \{}\sum _{i\in A}{\textbf {v}}(i)~{\Big |}~{\textbf {v}}\in P{\Big \}}$ for every $A\subseteq E$ .

The second property may be simplified to

If ${\textbf {u}},{\textbf {v}}\in P$ with $|{\textbf {v}}|>|{\textbf {u}}|$ , then $(\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {v}}({|E|})\})\in P.$

Then compactness is implied if $P$ is assumed to be bounded.

02Discrete polymatroids

A discrete polymatroid or integral polymatroid is a polymatroid for which the codomain of $f$ is $\mathbb {Z} _{\geq 0}$ , so the vectors are in $\mathbb {Z} _{\geq 0}^{E}$ instead of $\mathbb {R} _{\geq 0}^{E}$ . Discrete polymatroids can be understood by focusing on the lattice points of a polymatroid, and are of great interest because of their relationship to monomial ideals.

Discrete polymatroids are related to matroids. Given a positive integer $k$ , a discrete polymatroid $(E,f)$ (using the matroidal definition) is a $k$ -polymatroid if $f(e)\leq k$ for all $e\in E$ . Thus, a $1$ -polymatroid is a matroid. Also, for any discrete polymatroid $(E,f)$ , there is a matroid whose independent sets are the sets $A\subseteq E$ such that $f(U)\geq |U|$ for all $U\subseteq A$ .

03Relation to generalized permutahedra

A generalized permutahedron (alternative spelling: permutohedron) is a polytope whose normal fan is a coarsening of the braid fan, defined by the hyperplanes $x_{j}=x_{k}$ in $\mathbb {R} ^{n}$ ; note that the braid fan is the normal fan of the standard permutahedron. Thus the geometry of generalized permutahedra is intimately connected to the combinatorics of the symmetric group.

Alternatively, a generalized permutahedron can be characterized as a polytope obtained by parallel translations of the facets of the standard permutahedron. Thus $P$ is a generalized permutahedron precisely if

$P=\left\{x\in \mathbb {R} ^{n}:\,\sum _{i=1}^{n}x_{i}=z_{[n]},\ \sum _{i\in S}x_{i}\geq z_{S}\,{\text{ for all nonempty }}\,S\subseteq [n]\right\}$

for some submodular function $z:2^{[n]}\to \mathbb {R}$ .

The 0/1-polytopes among generalized permutahedra are precisely the matroid polytopes.

04Properties

$P_{f}$ is nonempty if and only if $f\geq 0$ and that $EP_{f}$ is nonempty if and only if $f(\emptyset )\geq 0$ .

Given any extended polymatroid $EP$ there is a unique submodular function $f$ such that $f(\emptyset )=0$ and $EP_{f}=EP$ .

05Contrapolymatroids

For a supermodular f one analogously may define the contrapolymatroid

${\Big \{}w\in \mathbb {R} _{\geq 0}^{E}~{\Big |}~\forall S\subseteq E,\sum _{e\in S}w(e)\geq f(S){\Big \}}$ .

This analogously generalizes the dominant of the spanning set polytope of matroids.

Watch videos about PolymatroidExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Polymatroid”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.