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 {\mathbb{ℝ}}_{\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=\{\text{x}\in {\mathbb{ℝ}}_{\ge 0}^E|\sum _{e\in U}\text{x}(e)\le f(U),\mathrm{\forall }U\subseteq E\}$.

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

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

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

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

The second property may be simplified to

If $\text{u},\text{v}\in P$ with $|\text{v}|>|\text{u}|$, then $(\max \{\text{u}(1),\text{v}(1)\},\dots ,\max \{\text{u}(|E|),\text{v}(|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{\mathbb{Z}}}_{\ge 0}$, so the vectors are in ${\mathbb{\mathbb{Z}}}_{\ge 0}^E$ instead of ${\mathbb{ℝ}}_{\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 ${\mathbb{ℝ}}^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 {\mathbb{ℝ}}^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 \mathbb{ℝ}$.

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 {\mathbb{ℝ}}_{\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

• Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge University Press, ISBN 0-521-01012-8 
• Fujishige, Satoru (2005), Submodular Functions and Optimization, Elsevier, ISBN 0-444-52086-4 
• Narayanan, H. (1997), Submodular Functions and Electrical Networks, Elsevier, ISBN 0-444-82523-1