Skip to main content
Source Link
Fedor Petrov
  • 108.8k
  • 9
  • 264
  • 459

If you have two matroids $M_1,M_2$ with rank functions $r_1,r_2$ on the same ground set $E$, the collection $M_1\cap M_2$ of subsets of $E$ which are independent in both $M_1$ and $M_2$ is not, in general, a matroid. However, there exists a minimax formula $$\max_{A\subset M_1\cap M_2} |A|=\min_{E=E_1\sqcup E_2} r_1(E_1)+r_2(E_2)$$ It leads to a polynomial algorithm to find the largest size of a set in $M_1\cap M_2$.

For 3 matroids, no formula, and the analogous problem becomes NP-hard.

Post Made Community Wiki by Fedor Petrov