In mathematics, a base-orderable matroid is a matroid that has the following additional property, related to the bases of the matroid.
there exists a feasible exchange bijection, defined as a bijection
are bases.The property was introduced by Brualdi and Scrimger.
[2][3] A strongly-base-orderable matroid has the following stronger property:For any two bases
, there is a strong feasible exchange bijection, defined as a bijection
are bases.Base-orderability imposes two requirements on the function
: Each of these properties alone is easy to satisfy: Every partition matroid is strongly base-orderable.
Recall that a partition matroid is defined by a finite collection of categories, where each category
has a capacity denoted by an integer
A basis of this matroid is a set which contains exactly
elements of each category
is a strong feasible exchange bijection.
Every transversal matroid is strongly base-orderable.
A notable example is the graphic matroid on the graph K4, i.e., the matroid whose bases are the spanning trees of the clique on 4 vertices.
[1] Denote the vertices of K4 by 1,2,3,4, and its edges by 12,13,14,23,24,34.
Note that the bases are: Consider the two bases A = {12,23,34} and B = {13,14,24}, and suppose that there is a function f satisfying the exchange property (property 2 above).
There are matroids that are base-orderable but not strongly-base-orderable.
[4][1] In base-orderable matroids, a feasible exchange bijection exists not only between bases but also between any two independent sets of the same cardinality, i.e., any two independent sets
This can be proved by induction on the difference between the size of the sets and the size of a basis (recall that all bases of a matroid have the same size).
If the difference is 0 then the sets are actually bases, and the property follows from the definition of base-orderable matroids.
to an independent set
to an independent set
Then, by the induction assumption there exists a feasible exchange bijection
is a feasible exchange bijection.
Then, the restriction of the modified function to
is a feasible exchange bijection.
The class of base-orderable matroids is complete.
This means that it is closed under the operations of minors, duals, direct sums, truncations, and induction by directed graphs.
[1]: 2 It is also closed under restriction, union and truncation.
[5]: 410 The same is true for the class of strongly-base-orderable matroids.