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

edit

Let   be a finite set and   a non-decreasing submodular function, that is, for each   we have  , and for each   we have  . We define the polymatroid associated to   to be the following polytope:

 .

When we allow the entries of   to be negative we denote this polytope by  , and call it the extended polymatroid associated to  .[2]

An equivalent definition

edit

Let   be a finite set. If   then we denote by   the sum of the entries of  , and write   whenever   for every   (notice that this gives an order to  ). A polymatroid on the ground set   is a nonempty compact subset   in  , the set of independent vectors, such that:

  1. We have that if  , then   for every  :
  2. If   with  , then there is a vector   such that  .

This definition is equivalent to the one described before,[3] where   is the function defined by   for every  .

Relation to matroids

edit

To every matroid   on the ground set   we can associate the set  , where   is the set of independent sets of   and we denote by   the characteristic vector of  : for every  

 

By taking the convex hull of   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

edit

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

edit

  is nonempty if and only if   and that   is nonempty if and only if  .

Given any extended polymatroid   there is a unique submodular function   such that   and  .

Contrapolymatroids

edit

For a supermodular f one analogously may define the contrapolymatroid

 

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

Discrete polymatroids

edit

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   they will live in  . This combinatorial object is of great interest because of their relationship to monomial ideals.

References

edit
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
  3. ^ J.Herzog, T.Hibi. Monomial Ideals. 2011. Graduate Texts in Mathematics 260, pp. 237–263 Springer-Verlag, London.


Additional reading