An integer analogue of Carathéodory's theorem (Q1074117): Difference between revisions

Denote by \({\mathbb{Z}}\) the integers and by \({\mathbb{Q}}\) the rationals. Consider a finite set \(A=\{a_ 1,...,a_ k\}\) in \({\mathbb{Z}}^ n\), and denote by \(C=\{\sum_{i}\alpha_ ia_ i: \alpha_ i\in {\mathbb{Q}},\quad \alpha_ i\geq 0\}\) the cone spanned by A. We call A a Hilbert basis for C, if every \(x\in C\cap {\mathbb{Z}}^ n\) can be expressed as a nonnegative integer combination of A. In analogy to Carathéodory's basic theorem for the real case, the authors prove that, in this situation, every \(x\in C\cap {\mathbb{Z}}^ n\) can be expressed as a nonnegative integer combination of no more than 2n-1 vectors in A, whenever C is linefree. They show that this last condition cannot be dropped and discuss the possibility of lowering the bound in question from 2n-1 to n. Various applications in integer programming, matroid theory and graph theory are brought to the readers attention.