Polymatroid
# 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 described as the multiset analogue of the matroid.

## Definition

Let $E$ be a finite set and $f:2^{E}\rightarrow \mathbb {R} _{+}$ 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} _{+}^{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$.

### An equivalent 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 an order to $\mathbb {R} _{+}^{E}$). A polymatroid on the ground set $E$ is a nonempty compact subset $P$ in $\mathbb {R} _{+}^{E}$, the set of independent vectors, such that:

* We have 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\subset E$.

## Relation to matroids

To every matroid $M$ on the ground set $E$ we can associate the set $V_{M}=\{{\textbf {w}}_{F}~|~F\in {\mathcal {I}}\}$, where ${\mathcal {I}}$ is the set of independent sets of $M$ and we denote by ${\textbf {w}}_{F}$ the characteristic vector of $F\subset E$: for every $i\in E$

${\textbf {w}}_{F}(i)={\begin{cases}1,&i\in F;\\0,&i\not \in F.\end{cases}}$

By taking the convex hull of $V_{M}$ we get a polymatroid. It is associated to the rank function of $M$. The conditions of the second definition reflect the axioms for the independent sets of a matroid.

## Relation to generalized permutahedra

Because generalized permutahedra can be constructed from submodular functions, and every generalized permutahedron has an associated submodular function, we have that 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 \w\in \mathbb {R} _{+}^{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.

## Discrete polymatroids

When we only focus on the lattice points of our polymatroids we get what is called, discrete polymatroids. Formally speaking, the definition of a discrete polymatroid goes exactly as the one for polymatroids except for where the vectors will live in, instead of $\mathbb {R} _{+}^{E}$ they will live in $\mathbb {Z} _{+}^{E}$. This combinatorial object is of great interest because of their relationship to monomial ideals.

