Matroid: rank is submodular

Dependencies:

  1. Matroid: rank
  2. Submodular function
  3. Matroid: rank of set increment
  4. Matroid: basis of set increment
  5. Matroid: expanding to basis

Let $M = (S, I)$ be a matroid. Then the rank function $r_M$ is submodular.

Proof

Let $X \subseteq Y \subseteq S$. Let $e \not\in Y$.

To prove that rank is submodular, we have to prove that $r(Y+e) - r(Y) \le r(X+e) - r(X)$. By the rank-of-increment theorem, $r(Y+e) - r(Y) \in \{0, 1\}$ and $r(X+e) - r(X) \in \{0, 1\}$. Therefore, it is sufficient to prove that if $r(Y+e) - r(Y) = 1$, then $r(X+e) - r(X) = 1$.

Let $B_X$ be a basis of $X$. Since $B_X$ is an independent set in $Y$, it can be expanded to a basis $B_Y$ of $Y$.

Since $r(Y+e) = r(Y) + 1$, $B_Y + e$ is a basis of $Y+e$. Since $B_X + e \subseteq B_Y + e$, $B_X + e \in I$ by the hierarchy axiom. Since $B_X + e \subseteq X + e$, $r(X+e) \ge |B_X + e| = r(X) + 1$. Therefore, $r(X+e) = r(X) + 1$.

Dependency for:

  1. Matroid: restricted rank is submodular

Info:

Transitive dependencies:

  1. /sets-and-relations/countable-set
  2. σ-algebra
  3. Matroid
  4. Matroid: rank
  5. Matroid: basis
  6. Matroid: basis iff size is rank
  7. Matroid: expanding to basis
  8. Matroid: basis of set increment
  9. Matroid: rank of set increment
  10. Set function
  11. Submodular function