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

Definition

Polyhedral definition

be a finite set a non-decreasing submodular function. We define the polymatroid to be the following polytope:

1. .

.

Matroidal definition

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 finite set is a non-decreasing submodular function. If the codomain is an integer polymatroid the ground set the rank function is independent is the polytope in the previous definition, called the independence polytope of the polymatroid.

, 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.

Vector definition

be a finite set (notice that this gives a partial order). A polymatroid is a nonempty compact such that:

This definition is equivalent to the one described before, is the function defined by

1. .

The second property may be simplified to

is assumed to be bounded.

Discrete polymatroids

A discrete polymatroid or integral polymatroid. 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.

(using the matroidal definition) is a -polymatroid.

Relation to generalized permutahedra

A generalized permutahedron (alternative spelling: permutohedron) is a polytope whose normal fan is a coarsening of the braid fan; 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. is a generalized permutahedron precisely if

.

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

Properties

is nonempty if and only if.

.

Contrapolymatroids

For a supermodular f one analogously may define the contrapolymatroid

1. .

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

References

1. Footnotes

   Additional reading