 Matroid independence polytope

For a finite matroid $M=(E,\mathcal{I})$, the convex hull of the indicator vectors of its matroid independent sets is exactly the displayed system, where $x(A)={\sum }_{e\in A}{x}_e$. It is an integral polytope. The equality $x(E)=r_M(E)$ instead gives the face corresponding to matroid bases; independence does not require that equality.

Proof. If $I$ is independent, $|I\cap A|\le r_M(A)$, so every independent indicator and every convex combination of them satisfies the inequalities. For the reverse inclusion, take an arbitrary real objective $c$. List its positive coordinates in nonincreasing order as $c_1\ge \cdots \ge c_k>0$, put $c_{k+1}=0$ and let $S_i$ be the first $i$ elements in this ordering. Run the matroid greedy algorithm on these elements, obtaining an independent set $I$. At every prefix the selected elements are maximal in $S_i$: an earlier rejected element cannot become admissible after further additions, by heredity. The augmentation axiom implies that every maximal independent set in $S_i$ has size $r_M(S_i)$. Hence $|I\cap S_i|=r_M(S_i)$.

For every point satisfying the displayed system, nonnegativity and telescoping giveThus every linear objective is maximized by an independent indicator, with the empty set used if all coefficients are nonpositive. Singleton rank inequalities bound every coordinate between zero and one, making the system compact. If it contained a point outside the compact convex hull of independent indicators, the finite-dimensional separating hyperplane theorem would supply an objective strictly larger at that point than at every independent indicator, a contradiction. This proves equality and integrality without assuming the desired convex-hull description in advance. Negative objective coefficients are discarded explicitly; maximizing over independent sets differs from maximizing over bases when such coefficients occur.