Rank (Matroid)

Definition

Rank (Matroid)

The rank $\mathrm{rank}(\mathcal{M})$ of a matroid is defined as the cardinality $|B|$ of any basis $B$ of $\mathcal{M}$, i.e.,

$$\mathrm{rank}(\mathcal{M})=r:⟺\exists B\in \mathcal{B}(\mathcal{M}):|B|=r.$$

Submodularity

Submodularity

Let $\mathcal{M}=(E,\mathcal{I})$ be a finite matroid with rank function $r$. For all $X,Y\subseteq E$,

$$r(X\cup Y)+r(X\cap Y)\le r(X)+r(Y).$$

Submodularity

Fix $X,Y\subseteq E$. We construct one independent set in $X\cup Y$ whose intersection with $X\cap Y$ already has the largest possible size.

Fill the intersection, then extend to the union

Choose an independent set $B\subseteq X\cap Y$ with $|B|=r(X\cap Y)$. Extend $B$ by adding elements of $X\cup Y$ while preserving independence, until no further element can be added. Call the resulting set $I$.

By exchangeability, a maximal independent subset of $X\cup Y$ has maximum size: a larger independent subset would supply another element to add. Hence

$$B\subseteq I\subseteq X\cup Y,|I|=r(X\cup Y).$$

Why the intersection stays exactly $B$

Suppose extending $B$ to $I$ added some $e\in (X\cap Y)\setminus B$. Since $B\subseteq I$, we would have

$$B\cup \{e\}\subseteq I.$$

By heredity, deleting elements from the independent set $I$ leaves an independent set. In particular, delete everything except $B$ and $e$:

Schematic: $B=\{b_1,b_2\}$ and $a,c$ are outside $X\cap Y$. The orange region contains the retained elements $B\cup \{e\}$, not necessarily all of $X\cap Y$. Deleting $a,c$ exposes an independent subset that is too large; the same argument works for any size of $B$.

The remaining set $B\cup \{e\}$ would therefore satisfy all three conditions:

$$\begin{array}{rlrl}B\cup \{e\}& \in \mathcal{I}& & \text{by heredity},\\ B\cup \{e\}& \subseteq X\cap Y& & \text{both B and e lie there},\\ |B\cup \{e\}|& =r(X\cap Y)+1& & \text{since e∈/B}.\end{array}$$

But an independent subset of $X\cap Y$ has size at most $r(X\cap Y)$. This would force

$$r(X\cap Y)+1=|B\cup \{e\}|\le r(X\cap Y),$$

a contradiction. Adding elements outside $X\cap Y$ cannot repair the dependent subset $B\cup \{e\}$. Thus extending $B$ to $I$ adds no further element of $X\cap Y$:

$$I\cap (X\cap Y)=B.$$

Bound the two portions

Both $I\cap X$ and $I\cap Y$ are independent, since they are subsets of $I$. By the definition of rank,

$$\begin{array}{rl}|I\cap X|& \le r(X),\\ |I\cap Y|& \le r(Y).\end{array}$$

Count the overlap twice

The two portions $I\cap X$ and $I\cap Y$ cover $I$ and overlap exactly in $B$. Adding their sizes counts every element of $I$ once, and every element of $B$ once more:

Shown for $I=\{a,b_1,b_2,c\}$ and $B=\{b_1,b_2\}$: each column is one element, and each dot is one occurrence in the sum. The same count gives, for arbitrary $I$ and $B$,

$$\begin{array}{rl}|I\cap X|+|I\cap Y|& =\underset{r(X\cup Y)}{\underbrace{|I|}}+\underset{r(X\cap Y)}{\underbrace{|B|}}\\ & \le r(X)+r(Y).\end{array}$$

This is the required inequality.

Function

Definition

Rank Function (Matroid)

The notion of ranks extends to arbitrary subsets. The rank function $r:2^E\to \mathbb{N}$ is

$$r(A)=\underset{Y\subseteq X}{\max }\{|Y|:Y\in \mathcal{I}\},\text{for all}X\subseteq E,$$

the size of the largest independent set inside $A$. The rank is $r(E)$.

Link to original