A polyhedron $P$ has the Integer Carath\'eodory Property if the following holds. For any positive integer $k$ and any integer vector $w$ in $kP$, there exist affinely independent integer vectors $x_1,\ldots,x_t$ in $P$ and positive integers $n_1,\ldots,n_t$ such that $n_1+\cdots+n_t=k$ and $w=n_1x_1+\cdots+n_tx_t$. In this paper we prove that if $P$ is a (poly)matroid base polytope or if $P$ is defined by a TU matrix, then $P$ and projections of $P$ satisfy the integer Carath\'eodory property.

, , , ,
Academic Press
Journal of Combinatorial Theory - Series B
Networks and Optimization

Gijswijt, D., & Regts, G. (2012). Polyhedra with the integer Caratheodory property. Journal of Combinatorial Theory - Series B, 102(1), 62–70.