Carathéodory rank

From Egres Open
Jump to: navigation, search

Let [math]A=\{a_1,\dots,a_k\}[/math] be a finite set of vectors in [math]{\mathbb Z}^n[/math]. The integer cone of A is the set of vectors arising as nonnegative integer combinations of vectors in A:

[math]\mbox{int.cone}(A)=\left\{\sum_{i=1}^{k} \lambda_i a_i:\ \lambda_i \in {\mathbb Z}_+\ (i=1,\dots,k)\right\}.[/math]

The Carathéodory rank of the set A is the smallest integer t such that every vector in int.cone(A) is the nonnegative integer combination of at most t vectors in A.

Sebő [1] proved that if A is a Hilbert basis, then the Carathéodory rank of A is at most [math]2n-2[/math]. Note that deciding if A is a Hilbert basis is a coNP-complete problem, even for 0-1 vectors [2]. Bruns et al.[3] showed an example where the Carathéodory rank is more than n (in fact, they showed that in n dimensions the maximal Carathéodory rank is at least [math]\lfloor 7/6 \rfloor n[/math]). It is open if it can be upper bounded by [math](2-\varepsilon)n[/math] for some [math]\varepsilon[/math].


  1. A. Sebő, Hilbert bases, Carathéodory’s theorem and combinatorial optimization, in: R. Kannan, W.R. Pulleyblank (Eds.), Integer Programming and Combinatorial Optimization, Univ. of Waterloo Press, Waterloo, Canada, 1990, pp. 431–455, Author link
  2. J. Pap, Recognizing conic TDI systems is hard, DOI link
  3. W. Bruns, J. Gubeladze, M. Henk, A. Martin, R. Weismantel, A counterexample to an integer analogue of Carathéodory’s theorem, J. Reine Angew. Math. 510 (1999) 179–185. DOI link, Author link