# 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 {R} _{\geq 0}$ 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} _{\geq 0}^{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$.

### 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 {R} _{\geq 0}$, or $\mathbb {Z} _{\geq 0},$ is a non-decreasing submodular function. If the codomain is $\mathbb {Z} _{\geq 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 {R} _{\geq 0}^{E}$ is independent if $\sum _{e\in U}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 {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 a partial order to $\mathbb {R} _{\geq 0}^{E}$). A polymatroid on the ground set $E$ is a nonempty compact subset $P$, the set of independent vectors, of $\mathbb {R} _{\geq 0}^{E}$ such 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\subseteq E$.
The second property may be simplified to
    If ${\textbf {u}},{\textbf {v}}\in P$ with $|{\textbf {v}}|>|{\textbf {u}}|$, then $(\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {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 {Z} _{\geq 0}$, so the vectors are in $\mathbb {Z} _{\geq 0}^{E}$ instead of $\mathbb {R} _{\geq 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)\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 \w\in \mathbb {R} _{\geq 0}^{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.