Is it true that for every connected matroid $M$ we have $\chi(M)=\chi(M^*)$?

48 Views Asked by At

If for any connected matroid $M$ on $E$ we let $\chi(M)$ be the minimum size of any partition of $E$ into independent sets of $M$, then is $\chi(M)=\chi(M^*)$? (where note $M^*$ is the dual of $M$ and $|E|>2$)

1

There are 1 best solutions below

0
On BEST ANSWER

This is not true. Consider a cycle graph $C_n$ and the corresponding matroid $M$. Then $\chi(M) = 2$. The dual is the matroid corresponding to the graph with two vertices and $n$ parallel edges between these vertices. It follows that $\chi(M^*) = n$.

More generally, if $M = U^r_n$ is a uniform matroid of rank $r$, then $\chi(M) = \lceil n / r\rceil$, while for $M^* = U_n^{n-r}$ we have $\chi(M^*) = \lceil n / (n-r) \rceil$, and these are not equal in general.