Polymatroid

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.

Definition

Polyhedral definition

Let ${\displaystyle E}$ be a finite set and ${\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}}$ 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 ${\displaystyle f(A)+f(B)\geq f(A\cup B)+f(A\cap B)}$ . We define the polymatroid associated to ${\displaystyle f}$ to be the following polytope:

${\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 ${\displaystyle {\textbf {x}}}$ to be negative we denote this polytope by ${\displaystyle EP_{f}}$ , and call it the extended polymatroid associated to ${\displaystyle f}$ .^[2]

Matroidal definition

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 ${\displaystyle (E,f)}$ where ${\displaystyle E}$ is a finite set and ${\displaystyle f:2^{E}\rightarrow \mathbb {R} _{\geq 0}}$ , or ${\displaystyle \mathbb {Z} _{\geq 0},}$ is a non-decreasing submodular function. If the codomain is ${\displaystyle \mathbb {Z} _{\geq 0},}$ we say that ${\displaystyle (E,f)}$ is an integer polymatroid. We call ${\displaystyle E}$ the ground set and ${\displaystyle f}$ the rank function of the polymatroid. This definition generalizes the definition of a matroid in terms of its rank function. A vector ${\displaystyle x\in \mathbb {R} _{\geq 0}^{E}}$ is independent if ${\displaystyle \sum _{e\in U}x(e)\leq f(U)}$ for all ${\displaystyle U\subseteq E}$ . Let ${\displaystyle P}$ denote the set of independent vectors. Then ${\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 ${\displaystyle 0}$ or ${\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.

Vector definition

Let ${\displaystyle E}$ be a finite set. If ${\displaystyle {\textbf {u}},{\textbf {v}}\in \mathbb {R} ^{E}}$ then we denote by ${\displaystyle |{\textbf {u}}|}$ the sum of the entries of ${\displaystyle {\textbf {u}}}$ , and write ${\displaystyle {\textbf {u}}\leq {\textbf {v}}}$ whenever ${\displaystyle {\textbf {v}}(i)-{\textbf {u}}(i)\geq 0}$ for every ${\displaystyle i\in E}$ (notice that this gives a partial order to ${\displaystyle \mathbb {R} _{\geq 0}^{E}}$ ). A polymatroid on the ground set ${\displaystyle E}$ is a nonempty compact subset ${\displaystyle P}$ , the set of independent vectors, of ${\displaystyle \mathbb {R} _{\geq 0}^{E}}$ such that:

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

${\displaystyle f(A)=\max {\Big \{}\sum _{i\in A}{\textbf {v}}(i)~{\Big |}~{\textbf {v}}\in P{\Big \}}}$ for every ${\displaystyle A\subseteq E}$ .

The second property may be simplified to

If ${\displaystyle {\textbf {u}},{\textbf {v}}\in P}$ with ${\displaystyle |{\textbf {v}}|>|{\textbf {u}}|}$ , then ${\displaystyle (\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {v}}({|E|})\})\in P.}$

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

Discrete polymatroids

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

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

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

$${\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 ${\displaystyle z:2^{[n]}\to \mathbb {R} }$ .

Properties

${\displaystyle P_{f}}$ is nonempty if and only if ${\displaystyle f\geq 0}$ and that ${\displaystyle EP_{f}}$ is nonempty if and only if ${\displaystyle f(\emptyset )\geq 0}$ .

Given any extended polymatroid ${\displaystyle EP}$ there is a unique submodular function ${\displaystyle f}$ such that ${\displaystyle f(\emptyset )=0}$ and ${\displaystyle EP_{f}=EP}$ .

Contrapolymatroids

For a supermodular f one analogously may define the contrapolymatroid

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

References

Footnotes

1. 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
2. Schrijver, Alexander (2003), Combinatorial Optimization, Springer, §44, p. 767, ISBN 3-540-44389-4
3. Welsh, D.J.A. (1976). Matroid Theory. Academic Press. p. 338. ISBN 0 12 744050 X.
4. J.Herzog, T.Hibi. Monomial Ideals. 2011. Graduate Texts in Mathematics 260, pp. 237–263 Springer-Verlag, London.
5. Postnikov, Alexander (2009), "Permutohedra, associahedra, and beyond", International Mathematics Research Notices, 2009 (6): 1026–1106, arXiv:math.CO/0507163, doi:10.1093/imrn/rnn153, MR 2487491

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