# 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 $\mbox{dim}(B)+1$.

## 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. D. Gijswijt, G. Regts, On the Caratheodory rank of polymatroid bases, March 2010, arXiv link.
2. D. Gijswijt, G. Regts, Polyhedra with the Integer Caratheodory Property, Journal of Combinatorial Theory Series B 102 (2012), 62–70, DOI link, arXiv link.
3. 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