Polymatroid

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Polymatroid" – news · newspapers · books · scholar · JSTOR (February 2011) (Learn how and when to remove this message)

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

Let E {\displaystyle E} be a finite set and f : 2 E → R ≥ 0 {\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}} a non-decreasing submodular function, 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 polytope:

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 \}}} .

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} .^[2]

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.^[3]

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.

Let E {\displaystyle E} be a finite set. 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 partial order to R ≥ 0 E {\displaystyle \mathbb {R} _{\geq 0}^{E}} ). A polymatroid on the ground set E {\displaystyle E} is a nonempty compact subset P {\displaystyle P} , the set of independent vectors, of R ≥ 0 E {\displaystyle \mathbb {R} _{\geq 0}^{E}} such that:

1. 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}}.}
2. 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|})\}).}

This definition is equivalent to the one described before,^[4] where f {\displaystyle f} is the function defined by

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} .

The second property may be simplified to

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.}

Then compactness is implied if P {\displaystyle P} is assumed to be bounded.

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 lattice points of a polymatroid, and are of great interest because of their relationship to monomial ideals.

Discrete polymatroids are related to matroids. 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. Also, for any discrete polymatroid ( E , f ) {\displaystyle (E,f)} , there is a matroid whose independent sets are the sets A ⊆ E {\displaystyle A\subseteq E} such that f ( U ) ≥ | U | {\displaystyle f(U)\geq |U|} for all U ⊆ A {\displaystyle U\subseteq A} .^[5]

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 {\displaystyle x_{j}=x_{k}} in R n {\displaystyle \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.^[6] Thus P {\displaystyle P} is a generalized permutahedron precisely if

P = { x ∈ R n : ∑ i = 1 n x i = z [ n ] ,   ∑ i ∈ S x i ≥ z S  for all nonempty  S ⊆ [ n ] } {\displaystyle P=\left\{x\in \mathbb {R} ^{n}:\,\sum _{i=1}^{n}x_{i}=z_{[n]},\ \sum _{i\in S}x_{i}\geq z_{S}\,{\text{ for all nonempty }}\,S\subseteq [n]\right\}}

for some submodular function z : 2 [ n ] → R {\displaystyle z:2^{[n]}\to \mathbb {R} } .

The 0/1-polytopes among generalized permutahedra are precisely the matroid polytopes.

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} .

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} .

For a supermodular f one analogously may define the contrapolymatroid

{ 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 \}}} .

This analogously generalizes the dominant of the spanning set polytope of matroids.

Footnotes

Additional reading

• Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge University Press, ISBN 0-521-01012-8
• Fujishige, Satoru (2005), Submodular Functions and Optimization, Elsevier, ISBN 0-444-52086-4
• Narayanan, H. (1997), Submodular Functions and Electrical Networks, Elsevier, ISBN 0-444-82523-1