Polyhedra with the Integer Carathéodory Property

AbstractA polyhedron P has the Integer Carathéodory Property if the following holds. For any positive integer k and any integer vector w∈kP, there exist affinely independent integer vectors x1,…,xt∈P and positive integers n1,…,nt such that n1+⋯+nt=k and w=n1x1+⋯+ntxt.In this paper we prove that if P is a (poly)matroid base polytope or if P is defined by a totally unimodular matrix, then P and projections of P have the Integer Carathéodory Property. For the matroid base polytope this answers a question by Cunningham from 1984