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

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

定理[独立集合]

独立集合の全体${\cal I}$は以下の条件をみたす。

1. ${\cal I}$の任意の元の任意の部分集合はまた${\cal I}$の元である。
2. ${\cal I}$の2元$I$と$J$に対して、$|J| > |I|$ならば、 $J\setminus I$の元$e$で$I\union\{e\}\in{\cal I}$なるものが存在する。

実はマトロイドは独立集合を与えることによっても定義することができて、 しかもその定義は基による定義と同値である。

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