Rank Function (Matroid)

discrete-mathematics combinatorics linear-algebra

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

Properties

The rank function satisfies the following properties:

Property

$$0\le \mathrm{rank}(X)\le |X|\forall X\subseteq E$$

Property

$$\mathrm{rank}(X)\le \mathrm{rank}(Y)\forall X\subseteq Y\subseteq E$$

Submodularity

$$\mathrm{rank}(X\cup Y)+\mathrm{rank}(X\cap Y)\le \mathrm{rank}(X)+\mathrm{rank}(Y)\forall X,Y\subseteq E$$