# Polymatroid

In mathematics, polymatroid is a polytope associated with a submodular function. The notion was introduced by Jack Edmonds in 1970.[1]

## Definition

Consider any submodular set function ${\displaystyle f}$ on ${\displaystyle E}$. Then define two associated polyhedra.

1. ${\displaystyle EP_{f}:=\{x\in \mathbb {R} ^{E}|\sum _{e\in U}x(e)\leq f(U),\forall U\subseteq E\}}$
2. ${\displaystyle P_{f}:=EP_{f}\cap \{x\in \mathbb {R} ^{E}|x\geq 0\}}$

Here ${\displaystyle P_{f}}$ is called the polymatroid and ${\displaystyle EP_{f}}$ is called the extended polymatroid associated with ${\displaystyle f}$.[2]

## Relation to matroids

If f is integer-valued, 1-Lipschitz, and ${\displaystyle f(\emptyset )=0}$ then f is the rank-function of a matroid, and the polymatroid is the independent set polytope, so-called since Edmonds showed it is the convex hull of the characteristic vectors of all independent sets of the matroid.

## Properties

${\displaystyle P_{f}}$ is nonempty if and only if ${\displaystyle f\geq 0}$ and that ${\displaystyle EP_{f}}$ is nonempty if and only if ${\displaystyle f(\emptyset )\geq 0}$.

Given any extended polymatroid ${\displaystyle EP}$ there is a unique submodular function ${\displaystyle f}$ such that ${\displaystyle f(\emptyset )=0}$ and ${\displaystyle EP_{f}=EP}$.

## Contrapolymatroids

For a supermodular f one analogously may define the contrapolymatroid

${\displaystyle w\in \mathbb {R} _{+}^{E}:\forall S\subseteq E,\sum _{e\in S}w(e)\geq f(S)}$

This analogously generalizes the dominant of the spanning set polytope of matroids.

## References

Footnotes
1. ^ Edmonds, Jack. Submodular functions, matroids, and certain polyhedra. 1970. Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) pp. 69–87 Gordon and Breach, New York. MR0270945
2. ^ Schrijver, Alexander (2003), Combinatorial Optimization, Springer, §44, p. 767, ISBN 3-540-44389-4