# Expressing vectors using bases of a matroid

Let *M* be a matroid on a ground-set of *n* elements, and *z* a vector which is the sum of the characteristic vectors of some bases. Can *z* be expressed as the non-negative integer-valued linear combination of at most *n* bases?

Dion Gijswijt and Guus Regts ^{[1]}^{[2]} proved that the answer is affirmative. Moreover, they proved the following more general theorem:

**Theorem ^{[1]}.** The Carathéodory rank of the bases of a base polytope

*B*equals [math]\mbox{dim}(B)+1[/math].

## Remarks

This would follow from the special case when "some" is *n*+1. It was proved by J. C. de Pina and J. Soares ^{[3]} that *z* can be expressed as the non-negative integer-valued linear combination of at most *n+r(M)* bases. Note that the conjecture is equivalent to the Carathéodory rank of the bases of a matroid being *n*.

## References

- ↑
^{1.0}^{1.1}D. Gijswijt, G. Regts,*On the Caratheodory rank of polymatroid bases*, March 2010, arXiv link. - ↑ D. Gijswijt, G. Regts,
*Polyhedra with the Integer Caratheodory Property*, Journal of Combinatorial Theory Series B 102 (2012), 62–70, DOI link, arXiv link. - ↑ J.C. de Pina, J. Soares,
*Improved Bound for the Carathéodory Rank of the Bases of a Matroid*, Journal of Combinatorial Theory Series B, Volume 88 , Issue 2 (July 2003), 323 - 327, DOI link