Polymatroid

This article needs additional citations for verification. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  –  ·  ·  · scholar · JSTOR (February 2011) (Learn how and when to remove this template message)

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

Definition[]

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

An equivalent definition[]

Let ${\displaystyle E}$ be a finite set and ${\displaystyle {\textbf {u}},{\textbf {v}}\in \mathbb {R} ^{E}}$. We call the modulus of ${\displaystyle {\textbf {u}}}$ to be the sum of all of its entries, denoted ${\displaystyle |{\textbf {u}}|}$, and denote ${\displaystyle {\textbf {u}}\leq {\textbf {v}}}$ whenever ${\displaystyle v_{i}-u_{i}\geq 0}$ for every ${\displaystyle i\in E}$ (notice that this gives an order to ${\displaystyle \mathbb {R} _{+}^{E}}$). A polymatroid on the ground set ${\displaystyle E}$ is a nonempty compact subset ${\displaystyle P}$ in ${\displaystyle \mathbb {R} _{+}^{E}}$, the set of independent vectors, such that:

1. We have that 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 w\in P}$ such that ${\displaystyle {\textbf {u}}<{\textbf {w}}\leq (\max\{u_{1},v_{1}\},\dots ,\max\{u_{|E|},v_{|E|}\})}$.

This definition is equivalent to the one described before,^[3] 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\subset E}$.

Relation to matroids[]

To every matroid ${\displaystyle M}$ on the ground set ${\displaystyle E}$ we can associate the set ${\displaystyle P_{M}=\{{\textbf {w}}_{F}~|~F\in M\}}$, where for every ${\displaystyle i\in E}$ we have that

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

By taking the convex hull of ${\displaystyle P_{M}}$ we get a polymatroid, in the sense of the second definition, associated to the rank function of ${\displaystyle M}$.

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[]

${\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 {\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 ${\displaystyle \mathbb {R} _{+}^{E}}$ they will live in ${\displaystyle \mathbb {Z} _{+}^{E}}$. This combinatorial object is of great interest because of their relationship to monomial ideals.

References[]

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, ISBN 0-444-82523-1