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.