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
