# Exchanges between independent sets of a matroid

Let $$I, J$$ be two bases of a matroid. For every $$x$$ in $$I$$, there is some $$y$$ in $$J$$ such that, if we exchange $$x$$ with $$y$$, then both resulting sets ($$I \setminus x \cup y$$ and $$J \setminus y \cup x$$) are bases (this is the strong basis exchange property).

Can we extend this property as follows: there exists a bijection $$f$$ between $$I\setminus J$$ and $$J\setminus I$$, such that for every $$x$$ in $$I$$, if we exchange $$x$$ with $$f(x)$$, then both resulting sets are bases?

The nearest result I found was in lecture notes by Goemans. In Lemma 5, he proves that there is a perfect matching between $$I\setminus J$$ and $$J\setminus I$$ in a bipartite graph that he denotes by $$D_M(I)$$. This means that for every $$x$$ in $$I$$, if we exchange $$x$$ with $$f(x)$$, then $$I \setminus x \cup f(x)$$ is a base. But, it does not imply that $$J \setminus f(x) \cup x$$ is a base too.

No, not every matroid satisfies this property. For example, it is known to fail for the cycle matroid of $$K_4$$. The matroids that satisfy your property are called base orderable matroids. There are important classes of matroids that are base orderable, such as transversal matroids. Moreover, base orderability is a minor-closed property, but Ingleton proved that there are actually an infinite number of excluded minors. See these slides of Joseph Bonin for more information. For example, the slides include a proof that $$M(K_4)$$ is not base orderable.