What is the proof that the rank of a matroid is sub-modular?

Question

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.

Answer 1

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$.

Answer 2

I am writing an answer to make sure I understand vadim's answer.

proof:

let $I_1 = \max_{I \in \mathcal{I}}\{|(A \cap B) \cap I|\}$, i.e., the maximal independent set of $A \cap B$. Recall the property of independent sets in matroids; if $|I| > |J|$ then there exists a sequence of elements $x_i \in I \setminus J$ such that at some point $|I| = |J \cup \{ x_1\} \cup ... \cup \{ x_k \}|$.

Now lets consider $I$, the maximal independent set of $A \cup B$. Obviously the size of $I$ cannot be less that $I_1$. i.e. $|I_1| \leq |I|$ (if the opposite where true, then clearly $I$ wouldn't be a maximally independent set of $A \cup B$!). Anyway, in the case where the inequality is strict $|I_1| < |I|$, then there exists one or more elements in $I$ not in $I_1$ that we can add to $I_1$ until $I_1$ matches in size to $I$. i.e. $|I| = |I_1 \cup \{ x_1\} ... \{ x_k \}|$.

Once that last equality is true then we can reason about where the elements $x_i$ came from.

Clearly, none of the $x_i$'s came from the intersection $A \cap B$, since if that were true, then $I_1$ wouldn't be maximal. Hence, they came from $A \setminus B$ or $B \setminus A$. Hence we have:

$$ I_1 \cup \{ x_1\} ... \{ x_k \} = I_1 \cup I_2 \cup I_3 $$

where $I_2 \subseteq A \setminus B$ and $I_3 \subseteq B \setminus A$.

Now $I_1 \cup I_2 \subseteq A$, however it might not be maximal. Hence $r(A) \geq |I_1| + |I_2|$. Similarly for $I_1 \cup I_3 \subseteq B$ we have $r(B) \geq |I_1| + |I_3|$.

Hence we get:

$r(A) + r(B) \geq |I_1| + |I_2| + |I_1| + |I_3|$

However, notice that $r(A \cup B) = |I| = |I_1 \cup I_2 \cup I_3| = |I_1| + |I_2| + |I_3|$ and $r(A \cap B) = |I_1|$. Hence:

$$r(A \cup B) + r(A \cap B) = |I_2| + 2|I_1| + |I_3|$$

Which Concludes the proof:

$r(A) + r(B) \geq |I_1| + |I_2| + |I_1| + |I_3| = r(A \cup B) + r(A \cap B)$

Answer 3

For a quick counterexample to equality, let $B$ be a basis and suppose there's an $e$ not in $B$ such that $C(e,B)$ is the the $B$-fundamental circuit of $e$. Then:

• $r(B) = r(M)$,
• $r(e) = 1$,
• $r(B \cup e) = r(M)$, and
• $r(B \cap e) = r(\emptyset) = 0$.