Английская Википедия: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.

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

The property in context

Base-orderability imposes two requirements on the function <math>f</math>:

1. It should be a bijection;
2. For every <math>a\in A\setminus B</math>, both <math>(A \setminus \{ a \}) \cup \{f(a)\}</math> and <math>(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>A</math> and <math>B</math> of a matroid satisfy the symmetric basis exchange property, which is that for every <math>a\in A\setminus B</math>, there exists some <math>f(a)\in B\setminus A</math>, such that both <math>(A \setminus \{ a \}) \cup \{f(a)\}</math> and <math>(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>a</math> are matched to the same <math>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>C_i</math> has a capacity denoted by an integer <math>d_i</math> with <math>0\le d_i\le |C_i|</math>. A basis of this matroid is a set which contains exactly <math>d_i</math> elements of each category <math>C_i</math>. For any two bases <math>A</math> and <math>B</math>, every bijection mapping the <math>d_i</math> elements of <math>C_i\cap A</math> to the <math>d_i</math> elements of <math>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>A</math> and <math>B</math> such that <math>|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>A</math> to an independent set <math>A\cup \{x\}</math> and augment <math>B</math> to an independent set <math>B\cup \{y\}</math>. Then, by the induction assumption there exists a feasible exchange bijection <math>f</math> between <math>A\cup \{x\}</math> and <math>B\cup \{y\}</math>. If <math>f(x)=y</math>, then the restriction of <math>f</math> to <math>A</math> and <math>B</math> is a feasible exchange bijection. Otherwise, <math>f^{-1}(y)\in A</math> and <math>f(x)\in B</math>, so <math>f</math> can be modified by setting: <math>f(f^{-1}(y)) := f(x)</math>. Then, the restriction of the modified function to <math>A</math> and <math>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.Шаблон:Rp It is also closed under restriction, union and truncation.Шаблон:Rp

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