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?

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

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'$.


Your Answer

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

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