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

マトロイド$M=(E,{\cal I})$は独立集合によって定義されているものとする。 $A\subset E$に対して、$A$に含まれる最大の独立集合の元の個数を、 $A$の階数と呼び、$\rho(A)$と書く。 前に定義した$M$の階数は、 $\rho(E)$に等しい。

$E$の部分集合$A$が独立であるための必要十分条件は、 $\rho(A)=|A|$が成り立つことである。 また次の定理が成り立つ。

定理[階数関数]

階数関数$\rho$は，以下の3条件をみたす。

1. 任意の$A\subset E$に対して、$0\le\rho(A)\le |A|$.
2. $A\subset B\subset E$ならば、$\rho(A)\le\rho(B)$.
3. 任意の$A,\,B\subset E$に対して、

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

実はマトロイドは階数関数によっても定義でき、しかもその定義は 独立集合による定義と (従って基による定義とも)同値である。

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