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.

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)\le 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)\ge |U|$ for all $U\subseteq A$.

Relation 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 ${ℝ}^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=\{x\in {ℝ}^n:\sum _{i=1}^n{x}_i=z_{[n]},\sum _{i\in S}{x}_i\ge z_S\text{ for all nonempty }S\subseteq [n]\}$$

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

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

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

• Template:Citation
• Template:Citation
• Template:Citation