Skip to main content
4 of 4
edited tags
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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.