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$
$\endgroup$
3
-
$\begingroup$ How is the matroid given? $\endgroup$– Gordon RoyleCommented Jan 20, 2015 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 AdamczykCommented Jan 20, 2015 at 17:33
-
$\begingroup$ Isn't the definition of strongly base-orderable that there is a bijection such that for every subset X of B1, that both B1 \ X + phi(X) AND B2 \ phi(X) + X are bases? I get this from here: en.wikipedia.org/wiki/Base-orderable_matroid $\endgroup$– Karagounis ZCommented Sep 14, 2021 at 18:18
Add a comment
|