階数関数

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

独立集合族構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\mathcal {I}}\,} をもつ$N\,$上のマトロイド $\mathbf {M} =(N,{\mathcal {I}})\,$ において, 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \rho (X)=\max\{|I|\mid I\subseteq X,\,I\in {\mathcal {I}}\}\,} で定められる関数 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 \,$ によってマトロイドを定義することもできる.