# Base orderable matroid

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

- 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

- ↑ 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.