Matroid independence polytope ($P_{\mathcal{I}}(M)=\{x\ge 0:x(A)\le 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 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.

For an undirected finite graph, its forest polytope is the matroid independence polytope of its graphic matroid. It has the exact inequality descriptionsHere $\kappa (V,A)$ counts all connected components of a graph, including isolated vertices, and $E(S)$ denotes the edges internal to $S$. A maximal forest has one fewer edge than vertices in each component, giving the rank $|V|-\kappa (V,A)$. The matroid independence polytope theorem therefore proves the first description. It implies the second since the rank of $E(S)$ is at most $|S|-1$. Conversely, split any $A$ into its vertex components $S_j$; nonnegativity gives $x(A)\le {\sum }_{j}x(E(S_j))\le {\sum }_j(|S_j|-1)=|V|-\kappa (V,A)$. No spanning requirement is imposed, so an optimum with negative edge weights can leave vertices isolated.