Polymatroid
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 formula_1 be a finite set and formula_2 a non-decreasing submodular function, that is, for each formula_3 we have formula_4, and for each formula_5 we have formula_6. We define the polymatroid associated to formula_7 to be the following polytope: formula_8. When we allow the entries of formula_9 to be negative we denote this polytope by formula_10, and call it the extended polymatroid associated to formula_11 . An equivalent definition. Let formula_1 be a finite set and formula_13. We call the "modulus" of formula_14 to be the sum of all of its entries, denoted formula_15, and denote formula_16 whenever formula_17 for every formula_18 (notice that this gives an order to formula_19). A polymatroid on the ground set formula_1 is a nonempty compact subset formula_21 in formula_22, the set of independent vectors, such that: This definition is equivalent to the one described before, where formula_7 is the function defined by formula_31 for every formula_32. Relation to matroids. To every matroid formula_33 on the ground set formula_1 we can  associate the set formula_35, where for every formula_36 we have that formula_37 By taking the convex hull of formula_38 we get a polymatroid, in the sense of the second definition, associated to the rank function of formula_39. 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. formula_40 is nonempty if and only if formula_41 and that formula_10 is nonempty if and only if formula_43. Given any extended polymatroid formula_44 there is a unique submodular function formula_11 such that formula_46 and formula_47. Contrapolymatroids. For a supermodular "f" one analogously may define the contrapolymatroid 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 formula_22 they will live in formula_50. This combinatorial object is of great interest because of their relationship to monomial ideals.