TR-2016-06

Base polyhedra and the linking property

Tamás Király



Abstract

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:

@techreport{egres-16-06,
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}
}


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