Packing common bases

Problems in this category

• Capacitated packing of k-arborescences
• Decomposition of oriented k-partition-connected digraphs
• Rota's conjecture on disjoint bases
• Scrambled Rota conjecture
• Strong colouring of matroid-graph pairs
• Upper bound on common independent set cover
• Woodall's conjecture

Introduction

One of the most intriguing questions in matroid theory is the status of packing common bases. This page intends to be a survey of known results and open questions related to this problem.

Let [math]M_1=(S,{\mathcal F}_1)[/math] and [math]M_2=(S,{\mathcal F}_2)[/math] be two matroids, and k a positive integer. We are interested in the following three problems:

• Can S be partitioned into k common independent sets of [math]M_1[/math] and [math]M_2[/math]?
• Does S contain k disjoint common bases of [math]M_1[/math] and [math]M_2[/math]?
• Does S contain k disjoint common spanning sets of [math]M_1[/math] and [math]M_2[/math]?

At first glance these problems may seem to be equivalent, and the first two are indeed closely related, but the third question is substantially different.

To our best knowledge, the time complexity of these problems under the rank oracle model is open. There are several known cases however, and several interesting conjectures can be formulated as a statement about packing common bases of two matroids.

Known cases

Strongly base orderable matroids

It was shown by Davies and McDiarmid that the problems are polynomially solvable for strongly base orderable matroids, and the obvious necessary conditions are sufficient.

Theorem. Let [math]M_1[/math] and [math]M_2[/math] be two strongly base orderable matroids on the same ground set S. If S can be partitioned into k independent sets in both [math]M_1[/math] and [math]M_2[/math], then S can be partitioned into k common independent sets.

Corollary. [math]M_1[/math] and [math]M_2[/math] have k disjoint common bases if and only if they have the same rank r and the matroids [math]k M_1[/math] and [math]k M_2[/math] have a common independent set of size [math]kr[/math].

Using the fact that the dual of a strongly base orderable matroid is strongly base orderable, we get the following corollary.

Corollary. [math]M_1[/math] and [math]M_2[/math] have k disjoint common spanning sets if and only if both matroids have k disjoint bases.

Disjoint branchings and connectors

Let D=(V,A) be a weakly connected directed graph, and let [math]r_0 \in V[/math] a node of in-degree 0. Let [math]M_1[/math] be the cycle matroid of the underlying undirected graph, and let [math]M_2[/math] be the partition matroid on ground set A where the edges entering a node v form a class for every [math]v \in V-r_0[/math]. The following statements are implied by Edmonds' disjoint arborescences theorem:

• [math]M_1[/math] and [math]M_2[/math] have k disjoint common bases if and only if the matroids [math]k M_1[/math] and [math]k M_2[/math] have a common independent set of size [math]kr[/math].
• A can be partitioned into k common independent sets if and only if A can be partitioned into k independent sets in both [math]M_1[/math] and [math]M_2[/math].

Interestingly, the corresponding statement about disjoint common spanning sets does not seem to follow from Edmonds' theorem, and to the best of our knowledge it is an open question. If [math]M_2[/math] is replaced by an arbitrary partition matroid, then the above statements do not necessarily hold.

The results of Keijsper and Schrijver on packing connectors can also be interpreted as results on disjoint common bases of two matroids which are obtained from a graphic matroid by contracting two sets which partition the node set.

Sufficient conditions

Using topological methods, Aharoni and Berger proved the following two results:

Theorem. Let [math]M_1[/math] and [math]M_2[/math] be two matroids on the ground set S with rank functions [math]r_1[/math] and [math]r_2[/math] respectively. If [math]2|X| \leq k \min\{r_1(X),r_2(X)\}[/math] for every [math]X \subseteq S[/math], then S can be partitioned into k common independent sets.

Theorem. If both [math]M_1[/math] and [math]M_2[/math] have 2k disjoint bases, then they have k disjoint common spanning sets.

Concerning the first theorem, Aharoni and Berger proposed a conjecture that would give the best possible upper bound:

For a loopless matroid [math]M=(S,r)[/math], let [math]\Delta(M)=\max_{X\subseteq S} |X|/r(X)[/math]. Let [math]M_1=(S,r_1)[/math] and [math]M_2=(S,r_2)[/math] be two arbitrary loopless matroids on S. Is it true that S can be partitioned into [math]\lceil\max\{\Delta(M_1),\Delta(M_2)\}\rceil+1[/math] common independent sets?

A element [math]v \in S[/math] is k-spanned in matroid M if there are k disjoint sets that span v. Kotlar and Ziv proved that if [math]M_1[/math] and [math]M_2[/math] are matroids on S and no element is 3-spanned in [math]M_1[/math] or [math]M_2[/math], then S can be partitioned into 2 common independent sets. They conjecture that this can be generalized to arbitrary k: if no element is (k+1)-spanned in [math]M_1[/math] or [math]M_2[/math], then S can be partitioned into k common independent sets.

Conjectures and questions

Rota's conjecture

Rota's beautiful conjecture states that if [math]M_1[/math] is a matroid of rank n whose ground set S can be partitioned into n disjoint bases [math]B_1,\dots,B_n[/math], and [math]M_2[/math] is the partition matroid with classes [math]B_1,\dots,B_n[/math], then [math]M_1[/math] and [math]M_2[/math] have n disjoint common bases. There are only a few partial results on this conjecture. Geelen and Humphries proved it for paving matroids.

For general matroids, Geelen and Webb proved that [math]M_1[/math] and [math]M_2[/math] have [math]\Omega(\sqrt{n})[/math] disjoint common bases. On the other hand, it follows from the results of Aharoni and Berger that S can be partitioned into 2n common independent sets.

Chow proposed a conjecture that would generalize Rota's, but this has been disproved by Harvey, Király and Lau . They also showed that if the problem of partitioning into common bases is polynomially solvable when [math]M_2[/math] is a partition matroid with classes independent in [math]M_1[/math], then it is polynomially solvable for any pair of matroids.

Further results related to Rota's conjecture can be found at the Open Problem Garden.

Woodall's conjecture

One of the most mysterious open problems in graph theory is Woodall's conjecture:

Is it true that if every directed cut in a digraph has at least k edges, then there are k disjoint dijoins?

Frank and Tardos showed that dijoins (more generally, k-dijoins for arbitrary k) of a digraph D can be described as projections of common bases of two matroids whose ground set contains the edge set of D. Therefore the problem of finding disjoint dijoins can be reduced to the problem of finding disjoint common bases. Moreover, one of the matroids is a partition matroid.

One consequence is that counterexamples for the Edmonds-Giles conjecture may be used to construct difficult examples for the common base packing problem. Such an example is presented by Harvey et al. as a counterexample to a conjecture of Chow.

Packing of k-arborescences

Let us consider the open problem Capacitated packing of k-arborescences:

Let D=(V,A) be a digraph with arc-capacities [math] c : A \to \mathbb{N}[/math] and a root node [math]r_0\in V[/math]. A k-arborescence is the arc-disjoint union of k spanning arborescences rooted at [math]r_0[/math]. Is it true that if [math]c(a)\leq l[/math] for every [math]a \in A[/math] and there is a capacity-obeying packing of kl spanning arborescences, then there is a capacity-obeying packing of l k-arborescences?

We define two matroids on a ground set S that consists of c(a) parallel arcs for every arc [math]a \in A[/math] (we say that these arcs correspond to a). In the first matroid [math]M_1[/math], a set of arcs is a base if it is the union of k disjoint spanning trees, and it contains at most one arc corresponding to a for every [math]a \in A[/math]. In the second matroid [math]M_2[/math], a set of arcs is a base if it contains exactly k arcs entering v for every [math]v \in V-r_0[/math]. It follows from Edmonds' disjoint arborescences theorem that the common bases of [math]M_1[/math] and [math]M_2[/math] are the k-arborescences with k(|V|-1) arcs.

The conjecture is equivalent to the following: if [math]lM_1[/math] and [math]lM_2[/math] have a common base of size kl(|V|-1), then [math]M_1[/math] and [math]M_2[/math] have l disjoint common bases. As we have seen, this type of statement is true for strongly base orderable matroids, but here [math]M_1[/math] is not strongly base orderable.

Clutters with the packing property

Let C be a clutter on ground set V. C is said to pack if the maximum number of disjoint elements of C equals the minimum size of a transversal of C. The clutter C has the packing property if every minor of C packs.

Characterizing clutters that pack (or have the packing property) seems to be very difficult. Several difficult theorems and open questions (e.g. the four colour theorem or Woodall's conjecture) can be formulated as a question about whether certain clutters pack.

For two matroids [math]M_1[/math] and [math]M_2[/math] we can consider the clutter [math]C(M_1,M_2)[/math] whose elements are the common bases of the two matroids. In general one may ask the following questions:

• For which pairs of matroids does [math]C(M_1,M_2)[/math] pack?
• For which pairs of matroids does [math]C(M_1,M_2)[/math] have the packing property?

Note that if [math]M_1=M_2[/math], then [math]C(M_1,M_2)[/math] packs if and only if the maximum number of disjoint bases equals the minimum size of a cut. This is not true in every matroid, for example it is not necessarily true in graphic matroids.