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 and there exists a feasible exchange bijection, defined as a bijection from to , such that for every , both and 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 and , there is a strong feasible exchange bijection, defined as a bijection from to , such that for every , both and are bases.

The property in context

Base-orderability imposes two requirements on the function :

  1. It should be a bijection;
  2. For every , both and 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 and of a matroid satisfy the symmetric basis exchange property, which is that for every , there exists some , such that both and are bases. However, it is not guaranteed that the resulting function f be a bijection - it is possible that several are matched to the same .

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 has a capacity denoted by an integer with . A basis of this matroid is a set which contains exactly elements of each category . For any two bases and , every bijection mapping the elements of to the elements of 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 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:

  • {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 and such that .

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 and augment to an independent set . Then, by the induction assumption there exists a feasible exchange bijection between and . If , then the restriction of to and is a feasible exchange bijection. Otherwise, and , so can be modified by setting: . 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.[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. 1 2 3 4 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.
  2. 1 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.