Base-orderable matroid

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 ${\displaystyle A}$ and ${\displaystyle B}$ there exists a feasible exchange bijection, defined as a bijection ${\displaystyle f}$ from ${\displaystyle A}$ to ${\displaystyle B}$, such that for every ${\displaystyle a\in A\setminus B}$, both ${\displaystyle (A\setminus \{a\})\cup \{f(a)\}}$ and ${\displaystyle (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 ${\displaystyle A}$ and ${\displaystyle B}$, there is a strong feasible exchange bijection, defined as a bijection ${\displaystyle f}$ from ${\displaystyle A}$ to ${\displaystyle B}$, such that for every ${\displaystyle X\subseteq A}$, both ${\displaystyle (A\setminus X)\cup f(X)}$ and ${\displaystyle (B\setminus f(X))\cup X}$ are bases.

The property in context

Base-orderability imposes two requirements on the function ${\displaystyle f}$:

1. It should be a bijection;
2. For every ${\displaystyle a\in A\setminus B}$, both ${\displaystyle (A\setminus \{a\})\cup \{f(a)\}}$ and ${\displaystyle (B\setminus \{f(a)\})\cup \{a\}}$ 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 ${\displaystyle A}$ and ${\displaystyle B}$ of a matroid satisfy the symmetric basis exchange property, which is that for every ${\displaystyle a\in A\setminus B}$, there exists some ${\displaystyle f(a)\in B\setminus A}$, such that both ${\displaystyle (A\setminus \{a\})\cup \{f(a)\}}$ and ${\displaystyle (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 ${\displaystyle a}$ are matched to the same ${\displaystyle 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 ${\displaystyle C_{i}}$ has a capacity denoted by an integer ${\displaystyle d_{i}}$ with ${\displaystyle 0\leq d_{i}\leq |C_{i}|}$. A basis of this matroid is a set which contains exactly ${\displaystyle d_{i}}$ elements of each category ${\displaystyle C_{i}}$. For any two bases ${\displaystyle A}$ and ${\displaystyle B}$, every bijection mapping the ${\displaystyle d_{i}}$ elements of ${\displaystyle C_{i}\cap A}$ to the ${\displaystyle d_{i}}$ elements of ${\displaystyle C_{i}\cap B}$ is a strong feasible exchange bijection.

Every transversal matroid is strongly base-orderable.[2]

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.[1] 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.[4][1]

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

References

1. Bonin, Joseph E.; Savitsky, Thomas J. (2016-01-01). "An infinite family of excluded minors for strong base-orderability". Linear Algebra and Its Applications. 488: 396–429. arXiv:1507.05521. doi:10.1016/j.laa.2015.09.055. ISSN 0024-3795. S2CID 119161534.
   • Joseph E. Bonin; Thomas J. Savitsky (April 2016). "Excluded Minors for (Strongly) Base-Orderable Matroids" (PDF).
2. Brualdi, Richard A.; Scrimger, Edward B. (1968-11-01). "Exchange systems, matchings, and transversals". Journal of Combinatorial Theory. 5 (3): 244–257. doi:10.1016/S0021-9800(68)80071-7. ISSN 0021-9800.
3. Brualdi, Richard A. (1969-08-01). "Comments on bases in dependence structures". Bulletin of the Australian Mathematical Society. 1 (2): 161–167. doi:10.1017/S000497270004140X. ISSN 1755-1633.
4. 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.
5. Oxley, James G. (2006), Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, ISBN 9780199202508.