Rank (Matroid)

discrete-mathematics combinatorics

Definition

Rank (Matroid)

The rank of a matroid $\mathcal{M}$ is the cardinality of any basis of $\mathcal{M}$.

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