# Covering the circuits of block matroids by paths

A matroid $M$ is strongly base orderable if for any two bases $A,B$ there exists a bijection $\varphi:A\to B$ such that $A-X+\varphi(X)$ is a basis for every $X\subseteq A$; note that this implies $B-\varphi(X)+X$ being a basis as well. Strongly base orderable matroids generalizes fundamental matroid classes that appear in combinatorial optimization problems, such as gammoids (and so partition, laminar, and transversal matroids). However, they do not include paving or graphic matroids, so the results for them are not applicable, for example, to graph theoretic problems.

A possible interpretation of strongly base orderability is as follows: for any pair $A,B$ of disjoint bases of a strongly base orderable matroid $M$, there exists a graph $G$ consisting of a matching between the elements of $A$ and $B$ such that $G$ covers every circuit of $M$ that lie in $A\cup B$. Here covering means that every circuit of $M$ spans at least one edge of $G$. As a relaxation of this property, we conjecture that an analogous statement holds for arbitrary matroids where $G$ is a path instead of a matching.

Conjecture 1. For disjoint bases $A,B$ of a matroid $M$, there exists a graph $G$ consisting of an alternating path between $A$ and $B$ such that $G$ covers every circuit of $M$ that lie in $A\cup B$.

Note that the elements of $A$ and $B$ have to appear alternatingly along the path. One might wonder: why a path is considered instead of a cycle? The path version seems to be stronger, but the two variants are in fact equivalent. Indeed, a path can simply be closed to get a cycle. To see the reverse implication, take the direct sum of the matroid with a uniform matroid of rank $1$ on the set ${a,b}$, that is, $A’:= A+a$ and $B’:= B+b$ are bases of the new matroid. Now arrange the elements of $A’$ and $B’$ around a cycle such that the elements of $A’$ and $B’$ receive odd and even numbers, respectively, and every circuit of the matroid contains two consecutive elements. As $a$ and $b$ are parallel in the extended matroid, they must follow each other in the cyclic ordering. Hence the path obtained after breaking up the cycle by deleting $a$ and $b$ satisfies the requirements of the conjecture.

A weaker version of the conjecture is also of interest. A matroid $M$ is base orderable if for any two bases $A,B$ there exists a bijection $\varphi:A\to B$ such that $A-a+\varphi(a)$ and $B+a-\varphi(a)$ are bases for every $a\in A$. In terms of covering circuits, this property is equivalent to the existence of a graph $G$ consisting of a matching between the elements of $A$ and $B$ such that $G$ covers the fundamental circuits of the elements of $A$ with respect to $B$, and the fundamental circuits of the elements of $B$ with respect to $A$. A relaxation of this property would be the following.

Conjecture 2. For disjoint bases $A,B$ of a matroid $M$, there exists a graph $G$ consisting of an alternating path between $A$ and $B$ such that $G$ covers $C(a,B)$ for $a\in A$ and $C(b,A)$ for $b\in B$.

The conjectures hold for graphic matroids, paving matroids, and spikes . However, they are wide open in general.

References
 K. Bérczi, T. Schwarcz, Partitioning into common independent sets via relaxing strongly base orderability, arXiv:2302.01445 (2023).