Matroid: rank

Dependencies:

  1. Matroid

Let $M = (S, I)$ be a matroid and $X \subseteq S$. Then rank of $X$, denoted as $\operatorname{rank}_M(X)$ or $r_M(X)$ is the size of the largest independent set in $X$.

Formally, the rank function $r_M: 2^S \mapsto \mathbb{N}$ is defined as \[ r_M(X) = \max_{\substack{Y \subseteq X \\ Y \in I}} |Y| \]

When it's clear from context which matroid we're talking about, then $r_M$ is usually simply denoted as $r$.

Dependency for:

  1. Matroid: rank of set increment
  2. Matroid: basis iff size is rank
  3. Matroid: rank is submodular
  4. Matroid: basis of set increment

Info:

Transitive dependencies:

  1. Matroid