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 described as the multiset analogue of the matroid.
Definition
Let E be a finite set and\( {\displaystyle f:2^{E}\rightarrow \mathbb {R} _{+}} \) a non-decreasing submodular function, that is, for each \( {\displaystyle A\subseteq B\subseteq E} \) we have \( {\displaystyle f(A)\leq f(B)} \), and for each \( {\displaystyle A,B\subseteq E} \)we have f\( {\displaystyle 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:
\( {\displaystyle P_{f}:=\left\{{\textbf {x}}\in \mathbb {R} _{+}^{E}~|~\sum _{e\in U}{\textbf {x}}(e)\leq f(U),\forall U\subseteq E\right\}}. \)
When we allow the entries of \( {\displaystyle {\textbf {x}}} \) to be negative we denote this polytope by \( EP_{f} \), and call it the extended polymatroid associated to f.[2]
An equivalent definition
Let E be a finite set and \( {\displaystyle {\textbf {u}},{\textbf {v}}\in \mathbb {R} ^{E}} \). We call the modulus of \( {\textbf {u}} \) to be the sum of all of its entries, and denote \( {\displaystyle {\textbf {u}}\leq {\textbf {v}}} \) whenever \( {\displaystyle v_{i}-u_{i}\geq 0} \) for \( {\displaystyle i\in E} \) (notice that this gives an order to \( {\displaystyle \mathbb {R} _{+}^{E}}) \). A polymatroid on the ground set E is a nonempty compact subset P in \( {\displaystyle \mathbb {R} _{+}^{E}} \), the set of independent vectors, such that:
We have that if \( {\displaystyle {\textbf {v}}\in P} \), then \( {\displaystyle {\textbf {u}}\in P} \) for every \( {\displaystyle {\textbf {u}}\leq {\textbf {v}}} \):
If \( {\displaystyle {\textbf {u}},{\textbf {v}}\in P} \) with \( {\displaystyle |{\textbf {v}}|>|{\textbf {u}}|} \), then there is a vector \( {\displaystyle w\in P} \) such that \( {\displaystyle {\textbf {u}}<{\textbf {w}}\leq (\max\{u_{1},v_{1}\},\dots ,\max\{u_{|E|},v_{|E|}\})}. \)
This definition is equivalent to the one described before[3], where f is the function defined by \( {\displaystyle f(A)=\max \left\{\sum _{i\in A}{\textbf {v}}(i)~|~{\textbf {v}}\in P\right\}} \) for every \( {\displaystyle A\subset E}. \)
Relation to matroids
To every matroid M on the ground set E we can associate the set \( {\displaystyle P_{M}=\{{\textbf {w}}_{F}~|~F\in M\}} \), where for every \( {\displaystyle i\in E} \) we have that
\( {\displaystyle {\textbf {w}}_{F}(i)={\begin{cases}1,&i\in F;\\0,&i\not \in F.\end{cases}}} \)
By taking the convex hull of \( {\displaystyle P_{M}} \) we get a polymatroid, in the sense of the second definition, associated to the rank function of M.
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
\( 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
\( {\displaystyle \left\{w\in \mathbb {R} _{+}^{E}:\forall S\subseteq E,\sum _{e\in S}w(e)\geq f(S)\right\}} \)
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 \( {\displaystyle \mathbb {R} _{+}^{E}} \) they will live in \( {\displaystyle \mathbb {Z} _{+}^{E}} \). This combinatorial object is of great interest because of their relationship to monomial ideals.
References
Footnotes
Edmonds, Jack. Submodular functions, matroids, and certain polyhedra. 1970. Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) pp. 69–87 Gordon and Breach, New York. MR0270945
Schrijver, Alexander (2003), Combinatorial Optimization, Springer, §44, p. 767, ISBN 3-540-44389-4
J.Herzog, T.Hibi. Monomial Ideals. 2011. Graduate Texts in Mathematics 260, pp. 237–263 Springer-Verlag, London.
Additional reading
Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge University Press, ISBN 0-521-01012-8
Fujishige, Saruto (2005), Submodular Functions and Optimization, Elsevier, ISBN 0-444-52086-4
Narayanan, H. (1997), Submodular Functions and Electrical Networks, ISBN 0-444-82523-1
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
