News

Relaxing strongly base orderability

The problem of covering the ground set of two matroids by a minimum number of common independent sets is notoriously hard even in very restricted settings, i.e.when the goal is to decide if two common independent sets suffice or not. However, Davies and McDiarmid showed that if both matroids are strongly base orderable, then the covering number of their intersection coincides with the maximum of their covering numbers.

Motivated by their result, in our recent paper Partitioning into common independent sets via relaxing strongly base orderability we propose relaxations of this property in two directions. First we weaken the basis-exchange condition, which leads to the definition of a new, complete class of matroids with distinguished algorithmic properties. Second, we introduce the notion of covering the circuits of a matroid by a graph, and consider the cases when the graph is ought to be 2-regular or a path. We give an extensive list of results explaining how the proposed relaxations compare to existing conjectures and theorems on coverings by common independent sets.