A matroid is said to be strongly base-orderable when for any two bases $B_1,B_2$ there exists a bijection $f:B_1 \mapsto B_2$ such that for any $X\subseteq B_1$ set $B_1 - X+ f(X)$ is also a base. Suppose we are given a matroid, but we don't know if it is SBO. How in polynomial time can we check the SBO condition?

  • $\begingroup$ How is the matroid given? $\endgroup$ – Gordon Royle Jan 20 '15 at 1:05
  • $\begingroup$ Good point. Suppose we are given two bases, and we want to see whether they satisfy the strong exchange property in time polynomial in the rank. Assume we have an oracle that given a set tells us whether it's independent. For weak orderability it is possible in polynomial time, i.e., just construct a graph of possible exchanges and find a perfect matching. My main interest is in understanding whether it's the same situation here as with Hall's theorem for perfect matchings --- we run an algorithm polynomial in the number of vertices, but then we know Hall's condition holds for all subsets. $\endgroup$ – Marek Adamczyk Jan 20 '15 at 17:33

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.