Base-orderable matroid explained

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

For any two bases

A

and
B

there exists a feasible exchange bijection, defined as a bijection f

from A

to
B

, such that for every
a\inA\setminusB

, both
(A\setminus\{a\})\cup\{f(a)\}

and
(B\setminus\{f(a)\})\cup\{a\}

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
A

and
B

, there is a strong feasible exchange bijection, defined as a bijection f

from A

to
B

, such that for every
X\subseteqA

, both
(A\setminusX)\cupf(X)

and
(B\setminusf(X))\cupX

are bases.

The property in context

Base-orderability imposes two requirements on the function

It should be a bijection;
For every

a\inA\setminusB

, both

(A\setminus\{a\})\cup\{f(a)\}

and

(B\setminus\{f(a)\})\cup\{a\}

should be bases.

Each of these properties alone is easy to satisfy:

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.
All bases

and

of a matroid satisfy the symmetric basis exchange property, which is that for every

a\inA\setminusB

, there exists some

f(a)\inB\setminusA

, such that both

(A\setminus\{a\})\cup\{f(a)\}

and

(B\setminus\{f(a)\})\cup\{a\}

are bases. However, it is not guaranteed that the resulting function f be a bijection - it is possible that several a

are matched to the same

f(a)

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

C_i

has a capacity denoted by an integer

d_i

with

0\led_i\le|C_i|

. A basis of this matroid is a set which contains exactly

d_i

elements of each category

C_i

. For any two bases

and

, every bijection mapping the

d_i

elements of

C_i\capA

to the

d_i

elements of

C_i\capB

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:

,, ;, ;, ; ;
, ;, ; ;
, ; .

Consider the two bases A = and B =, 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 \ + = which is not a basis; it cannot be 13, since B \ + = which is not a basis.
f(34) must equal 14: it cannot be 24, since B \ + = which is not a basis; it cannot be 13, since A \ + = 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.^[4]

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

and

such that

|A|=|B|

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

to an independent set

A\cup\{x\}

and augment

to an independent set

B\cup\{y\}

. Then, by the induction assumption there exists a feasible exchange bijection f

between

A\cup\{x\}

and

B\cup\{y\}

. If

f(x)=y

, then the restriction of f

to

and

is a feasible exchange bijection. Otherwise, f^-1(y)\inA

and f(x)\inB

, so f

can be modified by setting: f(f^-1(y)):=f(x)

. Then, the restriction of the modified function to

and

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.^[5]

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

Notes and References

2016-01-01. An infinite family of excluded minors for strong base-orderability. Linear Algebra and Its Applications. en. 488. 396–429. 1507.05521. 10.1016/j.laa.2015.09.055. 0024-3795 . Bonin. Joseph E.. Savitsky. Thomas J.. 119161534.
- Web site: Joseph E. Bonin . Thomas J. Savitsky . April 2016 . Excluded Minors for (Strongly) Base-Orderable Matroids .
Brualdi. Richard A.. Scrimger. Edward B.. 1968-11-01. Exchange systems, matchings, and transversals. Journal of Combinatorial Theory. en. 5. 3. 244–257. 10.1016/S0021-9800(68)80071-7. 0021-9800. free.
Brualdi. Richard A.. 1969-08-01. Comments on bases in dependence structures. Bulletin of the Australian Mathematical Society. en. 1. 2. 161–167. 10.1017/S000497270004140X. 1755-1633. free.
A.W. Ingleton. "Non-base-orderable matroids". In Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), pages 355–359. Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976.
.