Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Polymatroid
open-in-new
<h2 id="definition">Definition</h2> <h3>Polyhedral definition</h3> <p>Let E {\displaystyle E} be a finite <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> and f : 2 E → R ≥ 0 {\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}} a non-decreasing <a href="/facts/Submodular_set_function/YNnlKb4U">submodular function</a>, that is, for each A ⊆ B ⊆ E {\displaystyle A\subseteq B\subseteq E} we have f ( A ) ≤ f ( B ) {\displaystyle f(A)\leq f(B)} , and for each A , B ⊆ E {\displaystyle A,B\subseteq E} we have f ( A ) + f ( B ) ≥ f ( A ∪ B ) + f ( A ∩ B ) {\displaystyle f(A)+f(B)\geq f(A\cup B)+f(A\cap B)} . We define the polymatroid associated to f {\displaystyle f} to be the following <a href="/facts/Polytope/a76nXrL0">polytope</a>: </p><p> P f = { x ∈ R ≥ 0 E | ∑ e ∈ U x ( e ) ≤ f ( U ) , ∀ U ⊆ E } {\displaystyle 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 \}}} . </p><p>When we allow the entries of x {\displaystyle {\textbf {x}}} to be negative we denote this polytope by E P f {\displaystyle EP_{f}} , and call it the extended polymatroid associated to f {\displaystyle f} .<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p> <h3>Matroidal definition</h3> <p>In matroid theory, polymatroids are defined as the pair consisting of the set and the function as in the above definition. That is, a polymatroid is a pair ( E , f ) {\displaystyle (E,f)} where E {\displaystyle E} is a finite set and f : 2 E → R ≥ 0 {\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}} , or Z ≥ 0 , {\displaystyle \mathbb {Z} _{\geq 0},} is a non-decreasing submodular function. If the codomain is Z ≥ 0 , {\displaystyle \mathbb {Z} _{\geq 0},} we say that ( E , f ) {\displaystyle (E,f)} is an integer polymatroid. We call E {\displaystyle E} the ground set and f {\displaystyle f} the rank function of the polymatroid. This definition generalizes the definition of a matroid in terms of its rank function. A vector x ∈ R ≥ 0 E {\displaystyle x\in \mathbb {R} _{\geq 0}^{E}} is independent if ∑ e ∈ U x ( e ) ≤ f ( U ) {\displaystyle \sum _{e\in U}x(e)\leq f(U)} for all U ⊆ E {\displaystyle U\subseteq E} . Let P {\displaystyle P} denote the set of independent vectors. Then P {\displaystyle P} is the polytope in the previous definition, called the independence polytope of the polymatroid.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p><p>Under this definition, a matroid is a special case of integer polymatroid. While the rank of an element in a matroid can be either 0 {\displaystyle 0} or 1 {\displaystyle 1} , 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. </p> <h3>Vector definition</h3> <p>Let E {\displaystyle E} be a finite <a href="/facts/Set_(mathematics)/BfucfHMq">set</a>. If u , v ∈ R E {\displaystyle {\textbf {u}},{\textbf {v}}\in \mathbb {R} ^{E}} then we denote by | u | {\displaystyle |{\textbf {u}}|} the sum of the entries of u {\displaystyle {\textbf {u}}} , and write u ≤ v {\displaystyle {\textbf {u}}\leq {\textbf {v}}} whenever v ( i ) − u ( i ) ≥ 0 {\displaystyle {\textbf {v}}(i)-{\textbf {u}}(i)\geq 0} for every i ∈ E {\displaystyle i\in E} (notice that this gives a <a href="/facts/Partially_ordered_set/qb4a3FAX">partial order</a> to R ≥ 0 E {\displaystyle \mathbb {R} _{\geq 0}^{E}} ). A polymatroid on the ground set E {\displaystyle E} is a nonempty <a href="/facts/Compact_(mathematics)/d0cgXJH7">compact</a> subset P {\displaystyle P} , the set of independent vectors, of R ≥ 0 E {\displaystyle \mathbb {R} _{\geq 0}^{E}} such that: </p> <ol><li>If v ∈ P {\displaystyle {\textbf {v}}\in P} , then u ∈ P {\displaystyle {\textbf {u}}\in P} for every u ≤ v . {\displaystyle {\textbf {u}}\leq {\textbf {v}}.} </li> <li>If u , v ∈ P {\displaystyle {\textbf {u}},{\textbf {v}}\in P} with | v | > | u | {\displaystyle |{\textbf {v}}|>|{\textbf {u}}|} , then there is a vector w ∈ P {\displaystyle {\textbf {w}}\in P} such that u < w ≤ ( max { u ( 1 ) , v ( 1 ) } , … , max { u ( | E | ) , v ( | E | ) } ) . {\displaystyle {\textbf {u}}<{\textbf {w}}\leq (\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {v}}({|E|})\}).} </li></ol> <p>This definition is equivalent to the one described before,<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> where f {\displaystyle f} is the function defined by </p> f ( A ) = max { ∑ i ∈ A v ( i ) | v ∈ P } {\displaystyle f(A)=\max {\Big \{}\sum _{i\in A}{\textbf {v}}(i)~{\Big |}~{\textbf {v}}\in P{\Big \}}} for every A ⊆ E {\displaystyle A\subseteq E} . <p>The second property may be simplified to </p> If u , v ∈ P {\displaystyle {\textbf {u}},{\textbf {v}}\in P} with | v | > | u | {\displaystyle |{\textbf {v}}|>|{\textbf {u}}|} , then ( max { u ( 1 ) , v ( 1 ) } , … , max { u ( | E | ) , v ( | E | ) } ) ∈ P . {\displaystyle (\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {v}}({|E|})\})\in P.} <p>Then compactness is implied if P {\displaystyle P} is assumed to be bounded. </p> <h2 id="discrete-polymatroids">Discrete polymatroids</h2> <p>A discrete polymatroid or integral polymatroid is a polymatroid for which the codomain of f {\displaystyle f} is Z ≥ 0 {\displaystyle \mathbb {Z} _{\geq 0}} , so the vectors are in Z ≥ 0 E {\displaystyle \mathbb {Z} _{\geq 0}^{E}} instead of R ≥ 0 E {\displaystyle \mathbb {R} _{\geq 0}^{E}} . Discrete polymatroids can be understood by focusing on the <a href="/facts/Lattice_points/2ls9Iv9N">lattice points</a> of a polymatroid, and are of great interest because of their relationship to <a href="/facts/Monomial_ideal/UhogyF4z">monomial ideals</a>. </p><p>Given a positive integer k {\displaystyle k} , a discrete polymatroid ( E , f ) {\displaystyle (E,f)} (using the matroidal definition) is a k {\displaystyle k} -polymatroid if f ( e ) ≤ k {\displaystyle f(e)\leq k} for all e ∈ E {\displaystyle e\in E} . Thus, a 1 {\displaystyle 1} -polymatroid is a matroid. </p> <h2 id="relation-to-generalized-permutahedra">Relation to generalized permutahedra</h2> <p>Because <a href="/facts/Permutohedron/No1KH0rE">generalized permutahedra</a> 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. </p> <h2 id="properties">Properties</h2> <p> P f {\displaystyle P_{f}} is nonempty if and only if f ≥ 0 {\displaystyle f\geq 0} and that E P f {\displaystyle EP_{f}} is nonempty if and only if f ( ∅ ) ≥ 0 {\displaystyle f(\emptyset )\geq 0} . </p><p>Given any extended polymatroid E P {\displaystyle EP} there is a unique submodular function f {\displaystyle f} such that f ( ∅ ) = 0 {\displaystyle f(\emptyset )=0} and E P f = E P {\displaystyle EP_{f}=EP} . </p> <h2 id="contrapolymatroids">Contrapolymatroids</h2> <p>For a <a href="/facts/Supermodular/EkrRrU0f">supermodular</a> <i>f</i> one analogously may define the contrapolymatroid </p> { w ∈ R ≥ 0 E | ∀ S ⊆ E , ∑ e ∈ S w ( e ) ≥ f ( S ) } {\displaystyle {\Big \{}w\in \mathbb {R} _{\geq 0}^{E}~{\Big |}~\forall S\subseteq E,\sum _{e\in S}w(e)\geq f(S){\Big \}}} <p>This analogously generalizes the dominant of the <a href="/facts/Spanning_set/vPjclEtb">spanning set</a> <a href="/facts/Polytope/a76nXrL0">polytope</a> of matroids. </p> Footnotes Additional reading <ul><li><a href="/facts/Jon_Lee_(mathematician)/hnfK1FQN">Lee, Jon</a> (2004), <i>A First Course in Combinatorial Optimization</i>, <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-01012-8</li> <li>Fujishige, Satoru (2005), <i>Submodular Functions and Optimization</i>, <a href="/facts/Elsevier/jkPSAEmR">Elsevier</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-444-52086-4</li> <li>Narayanan, H. (1997), <i>Submodular Functions and Electrical Networks</i>, Elsevier, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-444-82523-1</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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 <a href="/wiki/MR_(identifier)" target="_blank">/wiki/MR_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Schrijver, Alexander (2003), Combinatorial Optimization, Springer, §44, p. 767, ISBN 3-540-44389-4 <a href="3-540-44389-4" target="_blank">3-540-44389-4</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Welsh, D.J.A. (1976). Matroid Theory. Academic Press. p. 338. ISBN 0 12 744050 X. <a href="0 12 744050 X" target="_blank">0 12 744050 X</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>J.Herzog, T.Hibi. Monomial Ideals. 2011. Graduate Texts in Mathematics 260, pp. 237–263 Springer-Verlag, London. <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> </ol>