= Matroid independence polytope
{title2=$P_{\mathcal I}(M)=\{x\geq0:x(A)\leq r_M(A)\text{ for all }A\subseteq E\}$}
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 <convex polytope>[polytope]. The equality $x(E)=r_M(E)$ instead gives the face corresponding to <matroid bases>; independence does not require that equality.
\b[Proof.] If $I$ is independent, $|I\cap A|\leq 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\geq\cdots\geq 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 give
$$
c^Tx\leq\sum_{j=1}^kc_jx_{e_j}
=\sum_{i=1}^k(c_i-c_{i+1})x(S_i)
\leq\sum_{i=1}^k(c_i-c_{i+1})r_M(S_i)
=c^T\mathbf1_I.
$$
Thus 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.
Back to article page
