Base polyhedra and the linking property

Tamás Király


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2016},
NUMBER = {TR-2016-06}

Last modification: 13.3.2018. Please email your comments to Tamás Király!