On the basis exchange property

One of the students in my class, Undergraduate Seminar on Discrete Mathematics, asks if the exchange property of a matroid can be strengthened to the following, of which I was completely unaware.

Strong basis exchange property. For every pair of bases B_1, B_2 and x_1 \in B_1, there exists x_2 \in B_2 such that both B_1 - x_1 + x_2 and B_2 + x_1 - x_2 are still bases.

As it turns out, Brualdi proved back in 1969 the strong exchange property (Theorem 2) in Comments on bases in dependence structures.

I record below the proof which showcases the benefit of viewing matroids both graphically and linear-algebraically.

As per Aaron Berger‘s suggestion, we use a graphic matroid to motivate the proof. Suppose T_1 and T_2 are two spanning trees of a connected graph G and e_1 is an edge in T_1. Clearly, when the edge e_1 is also in T_2, we can simply exchange e_1 with itself. Assume from now that e_1 is not in T_2. Note that T_2 + e_1 contains a unique cycle C, each edge of which can be “traded” to T_1. To be more precise, for every e_2 \in C, T_2 + e_1 - e_2 is still a spanning tree. It is then easy to see that adding back some edge from C - e_1 can reconnect the two connected components resulted from removing e_1 from T_1.

As the unique cycle (or circuit) C plays a central role in the above argument, one can show the same concept is valid in any matroid.

Lemma (Fundamental circuit). For every independent set I, if an element e satisfies that I + e is dependent, then I + e contains a unique circuit C, called the fundamental circuit. Moreover, for every f \in C, I + e - f is independent.

Proof of strong basis exchange property. Without loss of generality, we may assume that e_1 \not\in B_2. As B_2 is a maximal independent set and B_2 + e_1 is dependent, there is a unique circuit C \subseteq B_2 + e_1 such that B_2 + e_1 - e_2 is independent for every e_2 \in C.

Finally we resort to our intuition of representable matroids. Since e_1 \in \mathrm{span}(C - e_1) \subseteq \mathrm{span}(B_1 + C - e_1), we have \mathrm{span}(B_1 + C - e_1) = \mathrm{span}(B_1 + C), hence B_1 + C - e_1 contains a basis, say B_1'. By the ordinary exchange property for B_1 - e_1 and B_1', there is e_2 \in B_1' - (B_1 - e_1) \subseteq C - e_1 such that B_1 - e_1 + e_2 is independent. [qed]

Leave a comment

Your email address will not be published. Required fields are marked *