|
An integer polyhedron $P \subseteq \Rset^n$ has the linking property if for any
$f \in \Zset^n$ and $g \in \Zset^n$ with $f \leq g$, $P$ has an integer point between $f$ and $g$
if and only if it has both an integer point above $f$ and an integer point below $g$.
We prove that an integer polyhedron in the hyperplane $\sum_{j=1}^n x_j=\beta$
is a base polyhedron if and only if it has the linking property.
The result implies that an integer polyhedron has the strong linking property, as defined in
[A. Frank, T. Király, A survey on covering supermodular functions, 2009],
if and only if it is a generalized polymatroid.
Previous versions can be found here and here.
Bibtex entry:
| AUTHOR | = | {Kir{\'a}ly, Tam{\'a}s}, |
| TITLE | = | {Base polyhedra and the linking property}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2016}, |
| NUMBER | = | {TR-2016-06} |