階数関数によるマトロイドの定義

マトロイド$M = (E,{\cal I})$は、独立集合で定義されているとする。 $A$が$E$の部分集合であるとき、$A$に含まれる最大の独立集合の元の個数を、 $A$の階数と呼び、$\rho(A)$と書く。 ここで、上で定義した$M$の階数は、$\rho(E)$に等しい。

$E$の部分集合$A$が独立であるための必要十分条件は、$\rho(A)=|A|$が 成り立つことである。 ただし、$|A|$は$A$の元の個数とする。

また、$\rho$は次の3条件をみたす。

階数関数(i)

任意の$A \subset E$に対して、$0 \le \rho(A) \le |A|$.

階数関数(ii)

$A \subset B \subset E$ならば、$\rho(A) \le \rho(B)$.

階数関数(iii)

任意の$A,\, B \subset E$に対して、

\[ \rho (A \union B) + \rho (A \intersection B) \le \rho(A) + \rho(B). \]

有限集合$E$とその部分集合全体の族上定義され、上の３条件をみたす整数値関数$\rho$の 対$(E,\rho)$に対して、${\cal I} := \{I \subset E \; \rho(I) = |I|\}$と定義すると、 $(E,{\cal I})$は独立集合によるマトロイドの定義をみたし、 その階数関数は$\rho$に一致することが示される。