Base orderable matroid
Brualdi [1] showed that all matroids satisfy the following property: for any two bases [math]B_1[/math] and [math]B_2[/math] there is a bijection [math]f: B_1 \to B_2[/math] with the property that [math]B_1-e+f(e)[/math] is a base for any [math]e \in B_1[/math].
A matroid is weakly base orderable if for any two bases [math]B_1[/math] and [math]B_2[/math] there is a bijection [math]f: B_1 \to B_2[/math] with the property that [math]B_1-e+f(e)[/math] and [math]B_2-f(e)+e[/math] are bases for any [math]e \in B_1[/math].
A matroid is strongly base orderable if for any two bases [math]B_1[/math] and [math]B_2[/math] there is a bijection [math]g: B_1 \to B_2[/math] with the property that [math](B_1\setminus X)\cup g(X)[/math] is a base for any [math]X \subseteq B_1[/math].
Examples
- Every gammoid is strongly base orderable
- The matroid [math]P_7[/math] is strongly base orderable but not a gammoid (see [2] page 128)
- The matroid [math]P_8[/math] is weakly base orderable but not strongly base orderable
- The cycle matroid of [math]K_4[/math] is not weakly base orderable
Properties
Davies and McDiarmid [3] showed the following:
Theorem. If [math]M_1=(S,{\mathcal F}_1)[/math] and [math]M_2=(S,{\mathcal F}_2)[/math] are strongly base orderable matroids, and S can be partitioned into k independent subsets both in [math]M_1[/math] and in [math]M_2[/math], then S can be partitioned into k common independent sets of [math]M_1[/math] and [math]M_2[/math].
References
- ↑ Brualdi, R.A., Comments on bases in dependence structures, Bull. of the Australian Math. Soc. 1 (1969), 161–167, DOI link
- ↑ A.W. Ingleton, Transversal matroids and related structures, DOI link
- ↑ J. Davies and C. Mcdiarmid, Disjoint common transversals and exchange structures, J. London Math. Soc. 14 (1976), 55–62.DOI link.
