独立集合によるマトロイドの定義

マトロイド$M = (E,{\cal B})$は、前節の通り 定義されているものとする。 $E$の部分集合がある基に含まれているとき、その集合は独立(independent) であるという。 このとき${\cal B}$は、極大独立集合の全体に一致する。

独立集合の全体を${\cal I}$とすると、${\cal I}$は次の条件をみたす。

独立集合(i)

${\cal I}$の任意の元の任意の部分集合はまた${\cal I}$の元である。

独立集合(ii)

${\cal I}$の2元$I$と$J$に対して、$| J | > | I |$ならば、$J \setminus I$の元$e$で、 $I \union \{ e \}$が${\cal I}$の元であるものが存在する。

有限集合$E$とその部分集合の族${\cal I}$で上の2条件をみたすものの 対$(E,{\cal I})$に対して、${\cal I}$の極大元の全体を${\cal B}$とすると、 $(E,{\cal B})$は、基によるマトロイドの定義をみたし、 その独立集合の全体は${\cal I}$に一致することが示される。