Matroid Minor

interesting facts

, rank

number of optimal bases

unifrom:

graphic: (Cayley’s theorem, # spanning trees in complete graphs)

number of cut(or circuit?)

unifrom:

graphic: (Karger’s random global min cut algorithm)

minor

https://en.wikipedia.org/wiki/Matroid_minor

Fun2022 all your bases are belong to us

the maximal independent set does not affect the independent sets after contraction

suppose set has two maximal independent sets with the same size and there exists . matroid rank function is submodular. which means , a contradiction.

why dual?

这里 deletion 是直接在 ground set 里面删掉元素, contraction 就像 graph minor 一样, 把 element(边) 收缩. 区别是把 contract 掉的集合 的一个最大的 independent set 加入新的 matroid 的某个 independent set 里面的话, 得到的集合也必须是独立的.

用中文描述一下为啥 contraction 相当于在 dual matroid 上对同一个集合做 deletion 然后再取 dual. 原来的 matroid 是 , . 对于任意一个 的 base , 都有一个 cobase $T^* $. 得到的 matroid 的 base 是什么? 是 最小的 $T^* $. 也就是对应的 最大. 这样一来 contraction 之后的对偶得到的 matroid 的 base 就是 那些 再删掉所有 中的元素.

they are still matroids

1. deletion
   deletion 之后的 independent sets 是原来的子集, independent set exchange property 的话由于能选的sets在原来的matroid也是independent的, 而且exchange之后形成的新集合也不会包含X当中的元素, 也在新的independent set里面.
2. contraction
   
   1. empty set is independent ✔️
   2. hereditary property. ✔️
   3. independent set exchange property 和 deletion 的情况差不多, exchange 之后得到的集合 union T 也一定是 independent