A matroid $M = (E, \mathcal{I})$ consists of a ground set $E$ and a collection $\mathcal{I}$ of independent sets satisfying: (1) $\emptyset \in \mathcal{I}$; (2) if $A \in \mathcal{I}$ and $B \subseteq A$, then $B \in \mathcal{I}$ (hereditary); (3) if $A, B \in \mathcal{I}$ with $|A| < |B|$, then $\exists b \in B \setminus A$ with $A \cup \{b\} \in \mathcal{I}$ (augmentation). The rank $r(S) = \max\{|A| : A \subseteq S, A \in \mathcal{I}\}$.

Edmonds' matroid intersection theorem: The maximum size of a common independent set of matroids $M_1 = (E, \mathcal{I}_1)$ and $M_2 = (E, \mathcal{I}_2)$ equals $\min_{A \subseteq E}(r_1(A) + r_2(E \setminus A))$. This generalizes König's theorem (intersection of two partition matroids) and can be computed in polynomial time. Applications: common bases, colorful forests, and arborescences.

A set function $f: 2^E \to \mathbb{R}$ is submodular if $f(A) + f(B) \geq f(A \cup B) + f(A \cap B)$ for all $A, B$. Matroid rank functions are submodular. Lovász extension: any submodular function can be minimized in polynomial time via the ellipsoid method or combinatorial algorithms ($O(n^5 \gamma + n^6)$ where $\gamma$ is the evaluation cost). Submodular maximization is NP-hard in general but admits $(1-1/e)$-approximation for monotone submodular functions under cardinality constraints (Nemhauser-Wolsey-Fisher).