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\rightarrow \mathbb_$ 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\$.

When we allow the entries of $\textbf$ 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_$, or $\mathbb_,$ is a non-decreasing submodular function. If the codomain is $\mathbb_,$ 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_^E$ is independent if $\sum_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, \textbf \in \mathbb^E$ then we denote by $, \textbf,$ the sum of the entries of $\textbf$, and write $\textbf \leq \textbf$ whenever $\textbf(i)-\textbf(i)\geq 0$ for every $i \in E$ (notice that this gives a partial order to $\mathbb_^E$). A polymatroid on the ground set $E$ is a nonempty compact subset $P$, the set of independent vectors, of $\mathbb_^E$ such that:
# If $\textbf \in P$, then $\textbf \in P$ for every $\textbf\leq \textbf.$
# If $\textbf,\textbf \in P$ with $, \textbf, > , \textbf,$, then there is a vector $\textbf\in P$ such that $\textbf<\textbf\leq (\max\,\dots,\max\).$

This definition is equivalent to the one described before, where $f$ is the function defined by
:$f(A) = \max\Big\$ for every $A\subseteq E$.

The second property may be simplified to
:If $\textbf,\textbf \in P$ with $, \textbf, > , \textbf,$, then $(\max\,\dots,\max\)\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_$, so the vectors are in $\mathbb^E_$ instead of $\mathbb^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) \leq 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\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$.

Contrapolymatroids

For a supermodular ''f'' one analogously may define the contrapolymatroid
:$\Big\$
This analogously generalizes the dominant of the spanning set polytope of matroids.

References

;Footnotes

;Additional reading
*
*
*{{Citation, last=Narayanan, first=H., year= 1997 , title=Submodular Functions and Electrical Networks, publisher=Elsevier , isbn= 0-444-82523-1

Matroid theory