1
$\begingroup$

A matroid is said to be strongly base-orderable if for any two bases $B_1,B_2$ there is a bijection $f:B_1 \to B_2$ such that for any $S\subseteq B_1$ set $(B_1 \setminus S) \cup f(S)$ is also a base.

Are there strongly base-orderable matroids $M_k = (E, \mathcal{I}_k)$ for $k=1,2$ on the same ground set $E$, such that the union of $M_1$ and $M_2$ is not strongly base-orderable?

$\endgroup$
4
  • $\begingroup$ May I ask, what are the reasons to expect this to be true? $\endgroup$ Mar 26, 2015 at 7:33
  • $\begingroup$ I don't expect it to be true, but I didn't find a counterexample.. $\endgroup$ Mar 26, 2015 at 7:35
  • $\begingroup$ Well, this is a reason. Have you tried unions of gammoids? $\endgroup$ Mar 27, 2015 at 9:08
  • $\begingroup$ I haven't ... Can you construct an example? (I just formulated the question a bit differently.) $\endgroup$ Mar 27, 2015 at 9:48

1 Answer 1

3
$\begingroup$

Theorem 42.11 in A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, 2003 (he references Brualdi, Common Transversals and Strong Exchange Systems, 1970):

Any truncation of a strongly base orderable matroid is strongly base orderable again.

Given that, we may assume (w.l.o.g.) that $r(M_1 \vee M_2) = r(M_1) + r(M_2)$ since if not, then we may take an appropriate truncation $M_1'$ of $M_1$ such that $r(M) = r(M_1') + r(M_2)$. And $r(M_1 \vee M_2) = r(M_1) + r(M_2)$ gives us that the bases of $M_1 \vee M_2$ are given by $B_1 \cup B_2$ such that $B_1 \cap B_2 = \emptyset$ (where $B_i$ is a base of $M_i$). And in this case it is easy to see that we get the desired bijection $f: B_1 \cup B_2 \to B_1' \cup B_2'$ from the bijections $B_1 \to B_2$ and $B_1' \to B_2'$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.