Polymatroid 📖 Wikipedia

In mathematics, a polymatroid is a polytope associated with a submodular function. The notion was introduced by Jack Edmonds in 1970.^[1] It is also a generalization of the notion of a matroid.

Let ${\displaystyle E}$ be a finite set and ${\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}}$ a non-decreasing submodular function, that is, for each ${\displaystyle A\subseteq B\subseteq E}$ we have ${\displaystyle f(A)\leq f(B)}$, and for each ${\displaystyle A,B\subseteq E}$ we have ${\displaystyle f(A)+f(B)\geq f(A\cup B)+f(A\cap B)}$. We define the polymatroid associated to ${\displaystyle f}$ to be the following polytope:

${\displaystyle 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 ${\displaystyle {\textbf {x}}}$ to be negative we denote this polytope by ${\displaystyle EP_{f}}$, and call it the extended polymatroid associated to ${\displaystyle f}$.^[2]

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 ${\displaystyle (E,f)}$ where ${\displaystyle E}$ is a finite set and ${\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}}$, or ${\displaystyle \mathbb {Z} _{\geq 0},}$ is a non-decreasing submodular function. If the codomain is ${\displaystyle \mathbb {Z} _{\geq 0},}$ we say that ${\displaystyle (E,f)}$ is an integer polymatroid. We call ${\displaystyle E}$ the ground set and ${\displaystyle f}$ the rank function of the polymatroid. This definition generalizes the definition of a matroid in terms of its rank function. A vector ${\displaystyle x\in \mathbb {R} _{\geq 0}^{E}}$ is independent if ${\displaystyle \sum _{e\in U}x(e)\leq f(U)}$ for all ${\displaystyle U\subseteq E}$. Let ${\displaystyle P}$ denote the set of independent vectors. Then ${\displaystyle P}$ is the polytope in the previous definition, called the independence polytope of the polymatroid.^[3]

Under this definition, a matroid is a special case of integer polymatroid. While the rank of an element in a matroid can be either ${\displaystyle 0}$ or ${\displaystyle 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.

Let ${\displaystyle E}$ be a finite set. If ${\displaystyle {\textbf {u}},{\textbf {v}}\in \mathbb {R} ^{E}}$ then we denote by ${\displaystyle |{\textbf {u}}|}$ the sum of the entries of ${\displaystyle {\textbf {u}}}$, and write ${\displaystyle {\textbf {u}}\leq {\textbf {v}}}$ whenever ${\displaystyle {\textbf {v}}(i)-{\textbf {u}}(i)\geq 0}$ for every ${\displaystyle i\in E}$ (notice that this gives a partial order to ${\displaystyle \mathbb {R} _{\geq 0}^{E}}$). A polymatroid on the ground set ${\displaystyle E}$ is a nonempty compact subset ${\displaystyle P}$, the set of independent vectors, of ${\displaystyle \mathbb {R} _{\geq 0}^{E}}$ such that:

1. If ${\displaystyle {\textbf {v}}\in P}$, then ${\displaystyle {\textbf {u}}\in P}$ for every ${\displaystyle {\textbf {u}}\leq {\textbf {v}}.}$
2. If ${\displaystyle {\textbf {u}},{\textbf {v}}\in P}$ with ${\displaystyle |{\textbf {v}}|>|{\textbf {u}}|}$, then there is a vector ${\displaystyle {\textbf {w}}\in P}$ such that ${\displaystyle {\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,^[4] where ${\displaystyle f}$ is the function defined by

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

The second property may be simplified to

If ${\displaystyle {\textbf {u}},{\textbf {v}}\in P}$ with ${\displaystyle |{\textbf {v}}|>|{\textbf {u}}|}$, then ${\displaystyle (\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {v}}({|E|})\})\in P.}$

Then compactness is implied if ${\displaystyle P}$ is assumed to be bounded.

A discrete polymatroid or integral polymatroid is a polymatroid for which the codomain of ${\displaystyle f}$ is ${\displaystyle \mathbb {Z} _{\geq 0}}$, so the vectors are in ${\displaystyle \mathbb {Z} _{\geq 0}^{E}}$ instead of ${\displaystyle \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.

Discrete polymatroids are related to matroids. Given a positive integer ${\displaystyle k}$, a discrete polymatroid ${\displaystyle (E,f)}$ (using the matroidal definition) is a ${\displaystyle k}$-polymatroid if ${\displaystyle f(e)\leq k}$ for all ${\displaystyle e\in E}$. Thus, a ${\displaystyle 1}$-polymatroid is a matroid. Also, for any discrete polymatroid ${\displaystyle (E,f)}$, there is a matroid whose independent sets are the sets ${\displaystyle A\subseteq E}$ such that ${\displaystyle f(U)\geq |U|}$ for all ${\displaystyle U\subseteq A}$.^[5]

A generalized permutahedron (alternative spelling: permutohedron) is a polytope whose normal fan is a coarsening of the braid fan, defined by the hyperplanes ${\displaystyle x_{j}=x_{k}}$ in ${\displaystyle \mathbb {R} ^{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.^[6] Thus ${\displaystyle P}$ is a generalized permutahedron precisely if

$${\displaystyle P=\left\{x\in \mathbb {R} ^{n}:\,\sum _{i=1}^{n}x_{i}=z_{[n]},\ \sum _{i\in S}x_{i}\geq z_{S}\,{\text{ for all nonempty }}\,S\subseteq [n]\right\}}$$

for some submodular function ${\displaystyle z:2^{[n]}\to \mathbb {R} }$.

The 0/1-polytopes among generalized permutahedra are precisely the matroid polytopes.

${\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}$.

For a supermodular f one analogously may define the contrapolymatroid

${\displaystyle {\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.

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