Example Intersection Matroid is not a matroid.

1.4k Views Asked by At

Consider any two matroids $M_1=(E,\mathcal{I})$ and $M_2=(E,\mathcal{K})$ and let $\mathcal{Z}=\mathcal{I}\cap\mathcal{K}$. Can someone give an example where $(E,\mathcal{Z})=M_1 \cap M_2$ is not a matroid?

2

There are 2 best solutions below

1
On BEST ANSWER

Let $E = \{e, f, g, h\}$ and consider the following two collections of subsets of $E$ \begin{align*} \mathcal{I} &= \{\varnothing, \{e\},\{f\},\{g\},\{h\}, \{e,f\}, \{e,g\}, \{f,h\}, \{g,h\}\} ,\mbox{ and}\\ \mathcal{K} &= \{\varnothing, \{e\},\{f\},\{g\},\{h\}, \{e,f\}, \{e,h\}, \{f,g\}, \{g,h\}\}. \end{align*} Then, $M_1=(E,\mathcal{I})$ and $M_2=(E,\mathcal{K})$ are matroids. However, $$ \mathcal{Z} = \mathcal{I}\cap\mathcal{K} = \{\varnothing, \{e\},\{f\},\{g\},\{h\}, \{e,f\}, \{g,h\}\},$$ such that $(E, \mathcal{Z})$ is not a matroid.

2
On

Let $E = \{a, b, c\}$. Let $M_1$ be a rank $2$ matroid $(E, \mathcal{I})$ where every possible set is independent except $\{a,b\}$, and let $M_2$ be a rank $2$ matroid ($E$, $\mathcal{K}$) where every possible set is independent except $\{a,c\}$. If $(E, \mathcal{I} \cap \mathcal{K})$ is a matroid, then $a$ is a loop because it is not in any basis, but $\{a\}$ is an independent set; a contradiction.