Recall the definition of the rank of a matroid $(V, \mathcal{I})$:
$$ r(A) = \operatorname{rank}(A) = \max_{I \in \mathcal{I}}\{ | A \cap I | \} = \max\{ |I| : I \subseteq A, I \in \mathcal{I} \}$$
I was trying to prove that the rank of a matroid is a sub-modular function, i.e. that the following inequality holds for all subsets of the ground set (i.e. $\forall A, B \subseteq V$):
$$ r(A) + r(B) \geq r(A \cup B) + r(A \cap B)$$
I tried a "picture proof" by drawing a couple of sets and seeing how their intersection with independent elements behaved and I can only conclude that its in fact an equality. I am sure there is something wrong with that method and its not a real proof but wasn't sure how else to approach it. Does someone have a proof or a suggestion on good direction I might try to actually prove this result?
Also, is this suppose to be "intuitively obvious"? Because its not completely obvious for me.
Best Answer
Start with $I_1$ maximal independent in $A\cap B$. We have $r(A\cap B)=|I_1|$. By the property of independent sets, we may extend $I_1$ to $I$, maximal independent in $A\cup B$. We have $r(A\cup B)=|I|$. Now, partition $I=I_2\cup I_3\cup I_4$, where $I_2\in A\setminus B$, $I_3\in B\setminus A$, $I_4\in A\cap B$. By construction, $I_1\subseteq I_4$; however by the maximality of $I_1$, in fact $I_1=I_4$. Hence $r(A\cup B)=|I_1|+|I_2|+|I_3|$. This takes care of the RHS.
Now, $I_1\cup I_2$ is a subset of $I$, hence independent, and contained entirely in $A$. It might not be maximal independent in $A$, so all we can say is $r(A)\ge |I_1|+|I_2|$. By a similar argument $r(B)\ge |I_1|+|I_3|$.
Putting it all together, we get $$r(A)+r(B)\ge 2|I_1|+|I_2|+|I_3|=r(A\cup B)+r(A\cap B)$$
A bit more about the strictness. Suppose our ground set is the edges of a triangle graph (three vertices, three edges called $a,b,c$), with all cycle-free sets independent. That is, all subsets are independent, except all three edges together.
Set $A=\{a,b\}$, $B=\{a,c\}$. $r(A)=r(B)=2$, so LHS=$2+2=4$. $r(A\cap B)=1$, since $A\cap B=\{a\}$. However, $r(A\cup B)=2$, since $A\cup B=\{a,b,c\}$ yet all independent sets are of size 2 or less. Hence RHS=$2+1=3$.