<p>A <a href="https://en.wikipedia.org/wiki/Base-orderable_matroid" rel="nofollow noreferrer">base-orderable matroid</a> is a matroid in which, for any two bases <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, there exists a <em>feasible exchange bijection</em>, that is, a bijection <span class="math-container">$f: A\to B$</span> such that, for all <span class="math-container">$a\in A$</span>, both <span class="math-container">$A-a+f(a)$</span> and <span class="math-container">$B-f(a)+a$</span> are bases.</p>
<p>Given two bases of a base-orderable matroid, is it possible to compute a feasible exchange bijection in polynomial time?</p>
<p>All papers I found on this topic just consider the existence of such a bijection, but not its computation.</p>

CC BY-SA 4.0
2022-10-08T22:30:47.193Z
Doesn't this solve it? Build a bipartite graph on vertex set $A \cup B$. Put an edge $(a,b)$ iff A-a+b and B-b+a are both bases. Find a perfect matching.
Joshua Grochow
CC BY-SA 4.0
2022-10-09T00:00:00.980Z
@JoshuaGrochow you are right.. I did not think hard enough.
Erel Segal-Halevi
<ds.algorithms><co.combinatorics>
Computing a feasible exchange bijection between bases of a matroid
Erel Segal-Halevi
# Computing a feasible exchange bijection between bases of a matroid

(Asked by: username_0 on 2022-10-08)

A [base-orderable matroid](https://en.wikipedia.org/wiki/Base-orderable_matroid) is a matroid in which, for any two bases $A$ and $B$, there exists a *feasible exchange bijection*, that is, a bijection $f: A\to B$ such that, for all $a\in A$, both $A-a+f(a)$ and $B-f(a)+a$ are bases.

Given two bases of a base-orderable matroid, is it possible to compute a feasible exchange bijection in polynomial time?

All papers I found on this topic just consider the existence of such a bijection, but not its computation.

**Tags:** ds.algorithms, co.combinatorics

> **Comments:**
> **username_1**: Doesn't this solve it? Build a bipartite graph on vertex set $A \cup B$. Put an edge $(a,b)$ iff A-a+b and B-b+a are both bases. Find a perfect matching.  
> **username_0**: @JoshuaGrochow you are right.. I did not think hard enough.  

---

## 0 answers

