en.wikipedia.org

Polymatroid - Wikipedia

From Wikipedia, the free encyclopedia

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.

Polyhedral definition

[edit]

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

Matroidal definition

[edit]

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)$ where $E$ is a finite set and $f:2^{E}\rightarrow \mathbb {R} _{\geq 0}$ , or $\mathbb {Z} _{\geq 0},$ is a non-decreasing submodular function. If the codomain is $\mathbb {Z} _{\geq 0},$ we say that $(E,f)$ is an integer polymatroid. We call $E$ the ground set and $f$ the rank function of the polymatroid. This definition generalizes the definition of a matroid in terms of its rank function. A vector $x\in \mathbb {R} _{\geq 0}^{E}$ is independent if $\sum _{e\in U}x(e)\leq f(U)$ for all $U\subseteq E$ . Let $P$ denote the set of independent vectors. Then $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$ or $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$ be a finite set. If ${\textbf {u}},{\textbf {v}}\in \mathbb {R} ^{E}$ then we denote by $|{\textbf {u}}|$ the sum of the entries of ${\textbf {u}}$ , and write ${\textbf {u}}\leq {\textbf {v}}$ whenever ${\textbf {v}}(i)-{\textbf {u}}(i)\geq 0$ for every $i\in E$ (notice that this gives a partial order to $\mathbb {R} _{\geq 0}^{E}$ ). A polymatroid on the ground set $E$ is a nonempty compact subset $P$ , the set of independent vectors, of $\mathbb {R} _{\geq 0}^{E}$ such that:

If ${\textbf {v}}\in P$ , then ${\textbf {u}}\in P$ for every ${\textbf {u}}\leq {\textbf {v}}.$
If ${\textbf {u}},{\textbf {v}}\in P$ with $|{\textbf {v}}|>|{\textbf {u}}|$ , then there is a vector ${\textbf {w}}\in P$ such that ${\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$ is the function defined by

$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}}({|E|}),{\textbf {v}}({|E|})\})\in P.$

Then compactness is implied if $P$ is assumed to be bounded.

Discrete polymatroids

[edit]

A discrete polymatroid or integral polymatroid is a polymatroid for which the codomain of $f$ is $\mathbb {Z} _{\geq 0}$ , so the vectors are in $\mathbb {Z} _{\geq 0}^{E}$ instead of $\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.

Given a positive integer $k$ , a discrete polymatroid $(E,f)$ (using the matroidal definition) is a $k$ -polymatroid if $f(e)\leq k$ for all $e\in E$ . Thus, a $1$ -polymatroid is a matroid.

Relation to generalized permutahedra

[edit]

Because generalized permutahedra 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_{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$ .

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)\geq f(S){\Big \}}$

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

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. MR 0270945
^ Schrijver, Alexander (2003), Combinatorial Optimization, Springer, §44, p. 767, ISBN 3-540-44389-4
^ Welsh, D.J.A. (1976). Matroid Theory. Academic Press. p. 338. ISBN 0 12 744050 X.
^ 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, 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