Polymatroid Explained

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

be a finite set and

f:2^{E →}R₊

a non-decreasing submodular function, that is, for each

A\subseteqB\subseteqE

we have

f(A)\leqf(B)

, and for each

A,B\subseteqE

we have

f(A)+f(B)\geqf(A\cupB)+f(A\capB)

. We define the polymatroid associated to

to be the following polytope:

P_f=

	E~\|~\sum
\{bf{x}\inR
	e\inU

bf{x}(e)\leqf(U),\forallU\subseteqE\}

When we allow the entries of

bf{x}

to be negative we denote this polytope by

EP_f

, and call it the extended polymatroid associated to

An equivalent definition

Let

be a finite set. If

bf{u},bf{v}\inR^E

then we denote by

|bf{u}|

the sum of the entries of

bf{u}

, and write

bf{u}\leqbf{v}

whenever

bf{v}(i)-bf{u}(i)\geq0

for every

i\inE

(notice that this gives an order to

	E
R
	+

). A polymatroid on the ground set

is a nonempty compact subset

	E
R
	+

, the set of independent vectors, such that:

We have that if

bf{v}\inP

, then

bf{u}\inP

for every

bf{u}\leqbf{v}

bf{u},bf{v}\inP

with

|bf{v}|>|bf{u}|

, then there is a vector

bf{w}\inP

such that

bf{u}<bf{w}\leq(max\{bf{u}(1),bf{v}(1)\},...,max\{bf{u}({|E|}),bf{v}({|E|})\})

This definition is equivalent to the one described before, where

is the function defined by

f(A)=max\{\sum_i\inbf{v}(i)~|~bf{v}\inP\}

for every

A\subsetE

Relation to matroids

on the ground set

we can associate the set

V_M=\{bf{w}_F~|~F\inl{I}\}

, where

l{I}

is the set of independent sets of

and we denote by

bf{w}_F

the characteristic vector of

F\subsetE

: for every

i\inE

bf{w}_F(i)=\begin{cases}1,&i\inF;\ 0,&i\not\inF.\end{cases}

By taking the convex hull of

V_M

we get a polymatroid. It is associated to the rank function of

. 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\geq0

and that

EP_f

is nonempty if and only if

f(\emptyset)\geq0

Given any extended polymatroid

there is a unique submodular function

such that

f(\emptyset)=0

and

EP_f=EP

Contrapolymatroids

For a supermodular f one analogously may define the contrapolymatroid

\{w

	E~\|~\forall
\inR
	+

S\subseteqE,\sum_e\inw(e)\gef(S)\}

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

	E
R
	+

they will live in

	E
Z
	+

. This combinatorial object is of great interest because of their relationship to monomial ideals.

References

Footnotes

Additional reading