Polymatroid

A polymatroid on a finite ground set is the polytope defined by a normalized nondecreasing submodular function :

Its base polytope imposes the additional equality . For integer-valued , its integer bases are the nonnegative integer vectors in that base polytope. A matroid rank function is a special case; its integer bases are the incidence vectors of matroid bases. For and , the integer bases are . Counting common integer polymatroid bases counts vectors once, rather than their representations by labeled copies.

The integer bases also support an activity generating function, the polymatroid Tutte polynomial. For connected hypergraphs, the corresponding bases yield the hypergraph Tutte polynomial.