Base orderable matroid

From Egres Open
Jump to: navigation, search

Brualdi [1] showed that all matroids satisfy the following property: for any two bases $ B_1 $ and $ B_2 $ there is a bijection $ f: B_1 \to B_2 $ with the property that $ B_1-e+f(e) $ is a base for any $ e \in B_1 $.

A matroid is weakly base orderable if for any two bases $ B_1 $ and $ B_2 $ there is a bijection $ f: B_1 \to B_2 $ with the property that $ B_1-e+f(e) $ and $ B_2-f(e)+e $ are bases for any $ e \in B_1 $.

A matroid is strongly base orderable if for any two bases $ B_1 $ and $ B_2 $ there is a bijection $ g: B_1 \to B_2 $ with the property that $ (B_1\setminus X)\cup g(X) $ is a base for any $ X \subseteq B_1 $.

Examples

The linear representation of the matroids $ P_7 $ (2 dim) and $ P_8 $ (3 dim)
  • Every gammoid is strongly base orderable
  • The matroid $ P_7 $ is strongly base orderable but not a gammoid (see [2] page 128)
  • The matroid $ P_8 $ is weakly base orderable but not strongly base orderable
  • The cycle matroid of $ K_4 $ is not weakly base orderable


Properties

Davies and McDiarmid [3] showed the following:

Theorem. If $ M_1=(S,{\mathcal F}_1) $ and $ M_2=(S,{\mathcal F}_2) $ are strongly base orderable matroids, and S can be partitioned into k independent subsets both in $ M_1 $ and in $ M_2 $, then S can be partitioned into k common independent sets of $ M_1 $ and $ M_2 $.

References

  1. Brualdi, R.A., Comments on bases in dependence structures, Bull. of the Australian Math. Soc. 1 (1969), 161–167, DOI link
  2. A.W. Ingleton, Transversal matroids and related structures, DOI link
  3. J. Davies and C. Mcdiarmid, Disjoint common transversals and exchange structures, J. London Math. Soc. 14 (1976), 55–62.DOI link.