Suppose I have a matroid $M = (E, \mathcal{I})$. It is a known fact that given any two bases $X_0$ and $X_n$, we can transform $X_0$ into $X_n$ by repeatedly applying the basis exchange axiom. So there is a sequence of bases $X_0, \ldots, X_n$ such that $X_{i+1}$ is obtained by applying basis exchange to $X_i$ and $X_n$.

I am considering an extension of this. Suppose I have two bases $A_0$ and $B_0$ which partition the ground set. That is, $A_0$ and $B_0$ are disjoint bases whose union is the ground set $E$.

Now we are given two other bases $A_n$ and $B_n$. The goal is to transform the partition $A_0, B_0$ into $A_n, B_n$ by repeatedly applying symmetric basis exchange between $A_i$ and $B_i$ to obtain $A_{i+1}$ and $B_{i+1}$. In other words, we are looking for a sequence of partitions $A_0 \cup B_0, \ldots, A_n \cup B_n$ such that $A_i$ and $B_i$ are disjoint bases for each $i$ and $A_i \cup B_i = E$.

Is this always possible? Do we need to make some assumption about the matroid, such as base orderability?

Thank you



Your Answer

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

Browse other questions tagged or ask your own question.