Polymatroid

Let $E$ be a finite set and $f:\; 2^E\backslash rightarrow\; \backslash mathbb\{R\}\_\{\backslash geq\; 0\}$ a non-decreasing submodular function, that is, for each $A\backslash subseteq\; B\; \backslash subseteq\; E$ we have $f(A)\backslash leq\; f(B)$, and for each $A,\; B\; \backslash subseteq\; E$ we have $f(A)+f(B)\; \backslash geq\; f(A\backslash cup\; B)\; +\; f(A\backslash cap\; B)$. We define the polymatroid associated to $f$ to be the following polytope:

$P\_f=\; \backslash Big\backslash \{\backslash textbf\{x\}\backslash in\; \backslash mathbb\{R\}\_\{\backslash geq\; 0\}^E~\backslash Big|~\backslash sum\_\{e\backslash in\; U\}\backslash textbf\{x\}(e)\backslash leq\; f(U),\; \backslash forall\; U\backslash subseteq\; E\backslash Big\backslash \}$.

When we allow the entries of $\backslash textbf\{x\}$ to be negative we denote this polytope by $EP\_f$, and call it the extended polymatroid associated to $f$.

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\backslash rightarrow\; \backslash mathbb\{R\}\_\{\backslash geq\; 0\}$, or $\backslash mathbb\{Z\}\_\{\backslash geq\; 0\},$ is a non-decreasing submodular function. If the codomain is $\backslash mathbb\{Z\}\_\{\backslash 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\backslash in\; \backslash mathbb\{R\}\_\{\backslash geq\; 0\}^E$ is independent if $\backslash sum\_\{e\backslash in\; U\}x(e)\backslash leq\; f(U)$ for all $U\backslash 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.{{cite book |last1=Welsh |first1=D.J.A. |title=Matroid Theory |date=1976 |publisher=Academic Press |isbn=0 12 744050 X |page=338}}

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

1. If $\backslash textbf\{v\}\; \backslash in\; P$, then $\backslash textbf\{u\}\; \backslash in\; P$ for every $\backslash textbf\{u\}\backslash leq\; \backslash textbf\{v\}.$
2. If $\backslash textbf\{u\},\backslash textbf\{v\}\; \backslash in\; P$ with $|\backslash textbf\{v\}|>\; |\backslash textbf\{u\}|$, then there is a vector $\backslash textbf\{w\}\backslash in\; P$ such that

   E

   ),\textbf{v}(

   E

   )\}).

This definition is equivalent to the one described before, where $f$ is the function defined by

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

The second property may be simplified to

:If $\backslash textbf\{u\},\backslash textbf\{v\}\; \backslash in\; P$ with $|\backslash textbf\{v\}|>\; |\backslash textbf\{u\}|$, then $(\backslash max\backslash \{\backslash textbf\{u\}(1),\backslash textbf\{v\}(1)\backslash \},\backslash dots,\backslash max\backslash \{\backslash textbf\{u\}($

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

A discrete polymatroid or integral polymatroid is a polymatroid for which the codomain of $f$ is $\backslash mathbb\{Z\}\_\{\backslash geq\; 0\}$, so the vectors are in $\backslash mathbb\{Z\}^E\_\{\backslash geq\; 0\}$ instead of $\backslash mathbb\{R\}^E\_\{\backslash geq\; 0\}$. 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)\; \backslash leq\; k$ for all $e\; \backslash in\; E$. Thus, a $1$-polymatroid is a matroid.

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\backslash geq\; 0$ and that $EP\_f$ is nonempty if and only if $f(\backslash emptyset)\backslash geq\; 0$.

Given any extended polymatroid $EP$ there is a unique submodular function $f$ such that $f(\backslash emptyset)=0$ and $EP\_f=EP$.

For a supermodular f one analogously may define the contrapolymatroid

:$\backslash Big\backslash \{w\; \backslash in\backslash mathbb\{R\}\_\{\backslash geq\; 0\}^E~\backslash Big|~\backslash forall\; S\; \backslash subseteq\; E,\; \backslash sum\_\{e\backslash in\; S\}w(e)\backslash ge\; f(S)\backslash Big\backslash \}$

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

;Footnotes

{{reflist|30em|refs=

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. {{MathSciNet|id=0270945 }}

{{Citation|last=Schrijver|first=Alexander|author-link=Alexander Schrijver|year=2003|title=Combinatorial Optimization|publisher=Springer|isbn=3-540-44389-4|at=§44, p. 767}}

J.Herzog, T.Hibi. Monomial Ideals. 2011. Graduate Texts in Mathematics 260, pp. 237–263 Springer-Verlag, London.

}}

;Additional reading

• {{Citation|last=Lee|first=Jon|author-link=Jon Lee (mathematician)|year= 2004 |title=A First Course in Combinatorial Optimization |publisher=Cambridge University Press|isbn= 0-521-01012-8}}
• {{Citation|last=Fujishige|first=Satoru|year=2005|title=Submodular Functions and Optimization|publisher=Elsevier|isbn=0-444-52086-4}}
• {{Citation|last=Narayanan|first=H.|year= 1997 |title=Submodular Functions and Electrical Networks|publisher=Elsevier |isbn= 0-444-82523-1}}

Category:Matroid theory