階数関数

【かいすうかんすう (rank function)】

独立集合族${\mathcal {I}}\,$をもつ$N\,$上のマトロイド $\mathbf {M} =(N,{\mathcal {I}})\,$ において, $\rho (X)=\max\{|I|\mid I\subseteq X,\,I\in {\mathcal {I}}\}\,$ で定められる関数 $\rho :2^{N}\to \mathbf {Z} \,$ を階数関数という. 階数関数 $\rho \,$ は次の (R0)--(R3) を満たしている:

(R0) $\rho (\emptyset )=0\,$,

(R1) $\forall X\subseteq N\,$: $\rho (X)\leq |X|\,$,

(R2) $X\subseteq Y\Rightarrow \rho (X)\leq \rho (Y)\,$,

(R3) $\forall X,Y\subseteq N\,$: $\rho (X)+\rho (Y)\geq \rho (X\cap Y)+\rho (X\cup Y)\,$.

逆に, (R0)-(R3) を満たす関数 $\rho \,$ によってマトロイドを定義することもできる.