5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.