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.
be a finite set and
a non-decreasing submodular function, that is, for each
to be negative we denote this polytope by
, and call it the extended polymatroid associated to
[2] In matroid theory, polymatroids are defined as the pair consisting of the set and the function as in the above definition.
is a finite set and
is a non-decreasing submodular function.
the rank function of the polymatroid.
This definition generalizes the definition of a matroid in terms of its rank function.
denote the set of independent vectors.
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
, 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.
be a finite set.
(notice that this gives a partial order to
A polymatroid on the ground set
is a nonempty compact subset
, the set of independent vectors, of
is the function defined by The second property may be simplified to Then compactness is implied if
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.
Because generalized permutahedra can be constructed from submodular functions, and every generalized permutahedron has an associated submodular function, 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.
there is a unique submodular function
For a supermodular f one analogously may define the contrapolymatroid This analogously generalizes the dominant of the spanning set polytope of matroids.