Base-orderable matroid

Short description: Mathematical structure

In mathematics, a base-orderable matroid is a matroid that has the following additional property, related to the bases of the matroid.

For any two bases [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] there exists a feasible exchange bijection, defined as a bijection [math]\displaystyle{ f }[/math] from [math]\displaystyle{ A }[/math] to [math]\displaystyle{ B }[/math], such that for every [math]\displaystyle{ a\in A\setminus B }[/math], both [math]\displaystyle{ (A \setminus \{ a \}) \cup \{f(a)\} }[/math] and [math]\displaystyle{ (B \setminus \{ f(a) \}) \cup \{a\} }[/math] are bases.

The property was introduced by Brualdi and Scrimger. A strongly-base-orderable matroid has the following stronger property:

For any two bases [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math], there is a strong feasible exchange bijection, defined as a bijection [math]\displaystyle{ f }[/math] from [math]\displaystyle{ A }[/math] to [math]\displaystyle{ B }[/math], such that for every [math]\displaystyle{ X\subseteq A }[/math], both [math]\displaystyle{ (A \setminus X) \cup f(X) }[/math] and [math]\displaystyle{ (B \setminus f(X)) \cup X }[/math] are bases.

The property in context

Base-orderability imposes two requirements on the function [math]\displaystyle{ f }[/math]:

1. It should be a bijection;
2. For every [math]\displaystyle{ a\in A\setminus B }[/math], both [math]\displaystyle{ (A \setminus \{ a \}) \cup \{f(a)\} }[/math] and [math]\displaystyle{ (B \setminus \{ f(a) \}) \cup \{a\} }[/math] should be bases.

Each of these properties alone is easy to satisfy:

1. All bases of a given matroid have the same cardinality, so there are n! bijections between them (where n is the common size of the bases). But it is not guaranteed that one of these bijections satisfies property 2.
2. All bases [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] of a matroid satisfy the symmetric basis exchange property, which is that for every [math]\displaystyle{ a\in A\setminus B }[/math], there exists some [math]\displaystyle{ f(a)\in B\setminus A }[/math], such that both [math]\displaystyle{ (A \setminus \{ a \}) \cup \{f(a)\} }[/math] and [math]\displaystyle{ (B \setminus \{ f(a) \}) \cup \{a\} }[/math] are bases. However, it is not guaranteed that the resulting function f be a bijection - it is possible that several [math]\displaystyle{ a }[/math] are matched to the same [math]\displaystyle{ f(a) }[/math].

Matroids that are base-orderable

Every partition matroid is strongly base-orderable. Recall that a partition matroid is defined by a finite collection of categories, where each category [math]\displaystyle{ C_i }[/math] has a capacity denoted by an integer [math]\displaystyle{ d_i }[/math] with [math]\displaystyle{ 0\le d_i\le |C_i| }[/math]. A basis of this matroid is a set which contains exactly [math]\displaystyle{ d_i }[/math] elements of each category [math]\displaystyle{ C_i }[/math]. For any two bases [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math], every bijection mapping the [math]\displaystyle{ d_i }[/math] elements of [math]\displaystyle{ C_i\cap A }[/math] to the [math]\displaystyle{ d_i }[/math] elements of [math]\displaystyle{ C_i\cap B }[/math] is a strong feasible exchange bijection.

Every transversal matroid is strongly base-orderable.

Matroids that are not base-orderable

Some matroids are not base-orderable. A notable example is the graphic matroid on the graph K₄, i.e., the matroid whose bases are the spanning trees of the clique on 4 vertices. Denote the vertices of K₄ by 1,2,3,4, and its edges by 12,13,14,23,24,34. Note that the bases are:

• {12,13,14}, {12,13,24}, {12,13,34}; {12,14,23}, {12,14,34}; {12,23,24}, {12,23,34}; {12,24,34};
• {13,14,23}, {13,14,24}; {13,23,24}, {13,23,34}; {13,24,34};
• {14,23,24}, {14,23,34}; {14,24,34}.

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). Then:

• f(12) must equal 14: it cannot be 24, since A \ {12} + {24} = {23,24,34} which is not a basis; it cannot be 13, since B \ {13} + {12} = {12,14,24} which is not a basis.
• f(34) must equal 14: it cannot be 24, since B \ {24} + {34} = {13,14,34} which is not a basis; it cannot be 13, since A \ {34} + {13} = {12,13,23} which is not a basis.

Then f is not a bijection - it maps two elements of A to the same element of B.

There are matroids that are base-orderable but not strongly-base-orderable.

Properties

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 [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] such that [math]\displaystyle{ |A|=|B| }[/math].

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. Otherwise by the augmentation property of a matroid, we can augment [math]\displaystyle{ A }[/math] to an independent set [math]\displaystyle{ A\cup \{x\} }[/math] and augment [math]\displaystyle{ B }[/math] to an independent set [math]\displaystyle{ B\cup \{y\} }[/math]. Then, by the induction assumption there exists a feasible exchange bijection [math]\displaystyle{ f }[/math] between [math]\displaystyle{ A\cup \{x\} }[/math] and [math]\displaystyle{ B\cup \{y\} }[/math]. If [math]\displaystyle{ f(x)=y }[/math], then the restriction of [math]\displaystyle{ f }[/math] to [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] is a feasible exchange bijection. Otherwise, [math]\displaystyle{ f^{-1}(y)\in A }[/math] and [math]\displaystyle{ f(x)\in B }[/math], so [math]\displaystyle{ f }[/math] can be modified by setting: [math]\displaystyle{ f(f^{-1}(y)) := f(x) }[/math]. Then, the restriction of the modified function to [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] is a feasible exchange bijection.

Completeness

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. It is also closed under restriction, union and truncation.

The same is true for the class of strongly-base-orderable matroids.