# Generalized polymatroid

The term g-polymatroid is shorthand for "generalized polymatroid." The family of g-polymatroids includes the independent and spanning set polytopes of matroids.

## Definitions of Generalized Polymatroids

1. The original definition [1] of a g-polymatroid is any polyhedron of the form

$\{x \in \R^n \mid \forall S \subset [n] : p(S) \le x(S) \le b(S)\}$

where the set functions p, b are respectively super- and submodular, and they satisfy the cross-inequality $b(X) - p(Y) \ge b(X \backslash Y) - p(Y \backslash X)$ for all $X, Y \subset [n].$

1'. To write the previous definition more compactly, for $i \in [n]$ define a set-function $f_i$ on $[n] \backslash \{i\}$ by $f_i(S) := f(S \cup \{i\})-f(S).$ Then equivalent conditions on b and p are that for all i, $b_i$ is monotonically nonincreasing, $p_i$ is monotonically nondecreasing, and $b_i(S) \ge p_i(T)$ for all disjoint S, T.

2. A second equivalent definition [1][2][3] is that a g-polymatroid is a polyhedron obtained by taking a base polyhedron and applying a projection which deletes some coordinates.

3. For full-dimensional polyhedra, the following is also equivalent [4]: a full-dimensional polyhedron of the form

$\{x \in \R^n \mid Ax\le b, Ax' \ge b'\} ~~~~~~ \textrm{where}~A~\textrm{and}~A'~\textrm{are 0-1 matrices}$

is a g-polymatroid if and only if for every bounded primal objective, there is an optimal dual whose support corresponds to a laminar family. (Here, each dual variable corresponds to a row of A or A' and we identify these 0-1 n-vectors with subsets of [n] in the natural way.)

4. Integer g-polymatroids are exactly the polyhedra that satisfy the strong linking property [5].

As is typical with sub/supermodular polyhedra, one can still obtain a g-polymatroid even if the functions b and p have some subfamily of $2^{[n]}$ as their ground set, provided that certain "crossing" conditions hold; and if all the data defining the polyhedron are integral, then the polyhedron is integral. See the general references [2][6][7] for this and other facts.