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 a generalization of the notion of a matroid.

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=== Let E be a finite set and f: 2^E\rightarrow \mathbb{R}_{\geq 0} a non-decreasing submodular function, that is, for each A\subseteq B \subseteq E we have f(A)\leq f(B) , and for each A, B \subseteq E we have f(A)+f(B) \geq f(A\cup B) + f(A\cap B) . We define the polymatroid associated to f to be the following polytope: P_f= \Big\{\textbf{x}\in \mathbb{R}_{\geq 0}^E~\Big|~\sum_{e\in U}\textbf{x}(e)\leq f(U), \forall U\subseteq E\Big\} . When we allow the entries of \textbf{x} to be negative we denote this polytope by EP_f , and call it the extended polymatroid associated to f . f(A) = \max\Big\{\sum_{i\in A} \textbf{v}(i)~\Big|~ \textbf{v} \in P\Big\} for every A\subseteq E . The second property may be simplified to If \textbf{u},\textbf{v} \in P with |\textbf{v}|> |\textbf{u}| , then (\max\{\textbf{u}(1),\textbf{v}(1)\},\dots,\max\{\textbf{u}( ),\textbf{v}( )\})\in P. Then compactness is implied if P is assumed to be bounded. ==Relation to generalized permutahedra== A generalized permutahedron (alternative spelling: permutohedron) is a polytope whose normal fan is a coarsening of the braid fan, defined by the hyperplanes x_j = x_k in \mathbb{R}^n ; 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. Thus P is a generalized permutahedron precisely if P = \left\{ x \in \mathbb{R}^n : \, \sum_{i=1}^n x_i = z_{[n]}, \ \sum_{i \in S} x_i \ge z_S \, \text{ for all nonempty } \, S \subseteq [n] \right\} for some submodular function z: 2^{[n]} \to \mathbb{R} . The 0/1-polytopes among generalized permutahedra are precisely the matroid polytopes. ==Properties== P_f is nonempty if and only if f\geq 0 and that EP_f is nonempty if and only if f(\emptyset)\geq 0 . Given any extended polymatroid EP there is a unique submodular function f such that f(\emptyset)=0 and EP_f=EP . ==Contrapolymatroids== For a supermodular f one analogously may define the contrapolymatroid \Big\{w \in\mathbb{R}_{\geq 0}^E~\Big|~\forall S \subseteq E, \sum_{e\in S}w(e)\ge f(S)\Big\} . This analogously generalizes the dominant of the spanning set polytope of matroids. ==References== Footnotes Additional reading

Text derived from https://en.wikipedia.org/w/index.php?oldid=1353588377 under CC BY-SA 4.0; modifications have been made.