Polymatroid

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.

Definition

Polyhedral definition

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

$P_f=\{\mathbf{\text{𝐱}}\in {ℝ}_{\ge 0}^E|\sum _{e\in U}\mathbf{\text{𝐱}}(e)\le f(U),\mathrm{\forall }U\subseteq E\}$.

When we allow the entries of $\mathbf{\text{𝐱}}$ to be negative we denote this polytope by $E{P}_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\to {ℝ}_{\ge 0}$, or ${\mathbb{Z}}_{\ge 0},$ is a non-decreasing submodular function. If the codomain is ${\mathbb{Z}}_{\ge 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 {ℝ}_{\ge 0}^E$ is independent if $\sum _{e\in U}x(e)\le 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 $\mathbf{\text{𝐮}},\mathbf{\text{𝐯}}\in {ℝ}^E$ then we denote by $|\mathbf{\text{𝐮}}|$ the sum of the entries of $\mathbf{\text{𝐮}}$, and write $\mathbf{\text{𝐮}}\le \mathbf{\text{𝐯}}$ whenever $\mathbf{\text{𝐯}}(i)-\mathbf{\text{𝐮}}(i)\ge 0$ for every $i\in E$ (notice that this gives a partial order to ${ℝ}_{\ge 0}^E$). A polymatroid on the ground set $E$ is a nonempty compact subset $P$, the set of independent vectors, of ${ℝ}_{\ge 0}^E$ such that:

1. If $\mathbf{\text{𝐯}}\in P$, then $\mathbf{\text{𝐮}}\in P$ for every $\mathbf{\text{𝐮}}\le \mathbf{\text{𝐯}}.$
2. If $\mathbf{\text{𝐮}},\mathbf{\text{𝐯}}\in P$ with $|\mathbf{\text{𝐯}}|>|\mathbf{\text{𝐮}}|$, then there is a vector $\mathbf{\text{𝐰}}\in P$ such that $\mathbf{\text{𝐮}}<\mathbf{\text{𝐰}}\le (\max \{\mathbf{\text{𝐮}}(1),\mathbf{\text{𝐯}}(1)\},\dots ,\max \{\mathbf{\text{𝐮}}(|E|),\mathbf{\text{𝐯}}(|E|)\}).$

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

$f(A)=\max \{\sum _{i\in A}\mathbf{\text{𝐯}}(i)|\mathbf{\text{𝐯}}\in P\}$ for every $A\subseteq E$.

The second property may be simplified to

If $\mathbf{\text{𝐮}},\mathbf{\text{𝐯}}\in P$ with $|\mathbf{\text{𝐯}}|>|\mathbf{\text{𝐮}}|$, then $(\max \{\mathbf{\text{𝐮}}(1),\mathbf{\text{𝐯}}(1)\},\dots ,\max \{\mathbf{\text{𝐮}}(|E|),\mathbf{\text{𝐯}}(|E|)\})\in P.$

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

Discrete polymatroids

A discrete polymatroid or integral polymatroid is a polymatroid for which the codomain of $f$ is ${\mathbb{Z}}_{\ge 0}$, so the vectors are in ${\mathbb{Z}}_{\ge 0}^E$ instead of ${ℝ}_{\ge 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.

Given a positive integer $k$, a discrete polymatroid $(E,f)$ (using the matroidal definition) is a $k$-polymatroid if $f(e)\le k$ for all $e\in E$. Thus, a $1$-polymatroid is a matroid.

Relation to generalized permutahedra

Because generalized permutahedra can be constructed from submodular functions, and every generalized permutahedron has an associated submodular function, there should be a correspondence between generalized permutahedra and polymatroids. In fact every polymatroid is a generalized permutahedron that has been translated to have a vertex in the origin. This result suggests that the combinatorial information of polymatroids is shared with generalized permutahedra.

Properties

$P_f$ is nonempty if and only if $f\ge 0$ and that $E{P}_f$ is nonempty if and only if $f(\mathrm{\varnothing })\ge 0$.

Given any extended polymatroid $EP$ there is a unique submodular function $f$ such that $f(\mathrm{\varnothing })=0$ and $E{P}_f=EP$.

Contrapolymatroids

For a supermodular f one analogously may define the contrapolymatroid

$\{w\in {ℝ}_{\ge 0}^E|\mathrm{\forall }S\subseteq E,\sum _{e\in S}w(e)\ge f(S)\}$.

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

References

Footnotes

Additional reading