= Submodularity of matroid rank
{title2=$r(A)+r(B)\geq r(A\cap B)+r(A\cup B)$}
The <rank of a matroid> is a <normalised set function>, a <monotone set function>, and a <submodular set function>. Adding one element increases it by at most one.
\b[Proof of <submodularity>.] Choose a maximal <matroid independent set> $I_0$ in $A\cap B$, extend it to a maximal <matroid independent set> $I_A$ in $A$, then extend it to one $I_U$ in $A\cup B$. The <matroid independence axioms> make their sizes $r(A\cap B)$, $r(A)$ and $r(A\cup B)$. Every element of $I_U\setminus I_A$ lies outside $A$, since otherwise it could be added to $I_A$ inside $A$. Hence $I_0\cup(I_U\setminus I_A)$ is an independent <subset> of $B$, so its size $r(A\cap B)+r(A\cup B)-r(A)$ is at most $r(B)$.
The remaining assertions follow from the definition of the <rank of a matroid>. The <empty set> has maximum independent size zero, increasing the available <subset> cannot reduce that maximum, and deleting a newly added element from an independent <subset> decreases its size by at most one.
Back to article page
