マトロイド（２）

有限集合 とその部分集合族 の組 がマトロイドになる例。
一番簡単なものは があるベクトル空間の有限部分集合、 が一次独立な部分集合の全体。
すると、マトロイドの定義における最初の二つは自明で、最後は

が一次独立で のときに、 に含まれるベクトル で が一次独立なものが存在する

という意味になる。これは学部線型代数の次元と基底の議論をするあたりの練習問題。

もうひとつの典型的な例は無向グラフ において、 を枝集合 の部分集合で、ループを含まないもの、とすると はマトロイドである。これがいわゆるグラフ的マトロイド。

定義ばかりやっていても面白くないのだけれど、グラフのいろいろな不変量をマトロイドに拡張する例をいくつか挙げると面白くなりそう。彩色多項式が出てきたり、さらに一般化した Tutte 多項式が定義できたりする。