Reductions to partition matroids

Given two matroids $M=(S,\mathcal{I})$ and $N=(S,\mathcal{J})$, we say that $N$ is a reduction of $M$ if every independent set of $N$ is also independent in $M$, that is, $\mathcal{J}\subseteq\mathcal{I}$. We denote such a relation by $N\preceq M$. The reduction is rank-preserving if furthermore the ranks of $M$ and $N$ coincide, which is denoted by $N\preceq_r M$. In terms of weak maps, first defined by Crapo and Rota [3], a reduction corresponds to the identity weak map on the common ground set of the two matroids. In particular, if $N$ is a partition matroid (with upper bounds 1 on every partition class), then the reduction determines a coloring of the ground set such that $M$ contains no rainbow colored circuit.

The covering number of a loopless matroid $M=(S,\mathcal{I})$ is the minimum number of independent sets from $\mathcal{I}$ needed to cover the ground set $S$. We say that a matroid is $k$-coverable if its covering number is at most $k$. The notion of covering number can be straightforwardly extended to matroid intersection as the minimum number of common independent sets needed to cover $S$.

We have already seen that reductions to partition matroids can be identified with rainbow circuit-free colorings. As the covering number of a partition matroid is just the maximum size of the partition classes defining it, this parameter translates into the maximum size of a color class of the coloring. Motivated by the Aharoni-Berger conjecture [1] on the covering number of the intersection of two matroids, Bérczi, Schwarcz, and Yamaguchi [2] conjectured the following.

Conjecture 1. Every $k$-coverable matroid can be reduced to a $2\cdot k$-coverable partition matroid.

The conjecture holds for paving matroids, graphic matroids, and gammoids even with $2\cdot k-1$ in place of $2\cdot k$. However, Abdolazimi, Karlin, Klein, and Gharan [4] and Leichter, Moseley, and Pruhs [5] disproved it in general by showing that the statement fails for complete binary matroids of large enough rank. Their result was further generalized by Jorn van der Pol [6] who showed that a random subset of the rank-$n$ projective geometry $PG(n-1,q)$ is, with high probability, not $(b,c)$-decomposable. That is, if the covering number of the set is $k$, then it does not admit a partition of its ground set into classes of size at most $ck$, every transversal of which is $b$-coverable. However, it remains an open question whether the conjecture holds for small values of $k$, say, $k=2$.

Conjecture 2. Every 2-coverable matroid can be reduced to a 3-coverable partition matroid.

Another interesting question is whether there exists a reduction to a partition matroid whose covering number is bounded by a function of $k$.

Conjecture 3. There is a function $f$ such that every $k$-coverable matroid can be reduced to a $f(k)$-coverable partition matroid.

[1] R. Aharoni and E. Berger, The intersection of a matroid and a simplicial complex, Transactions of the American Mathematical Society, 358, pp. 4895–4917 (2006).
[2] K. Bérczi, T. Schwarcz, and Y. Yamaguchi, List colouring of two matroids through reduction to partition matroids, SIAM Journal on Discrete Mathematics, 35(3), pp. 2192-2209 (2021).
[3] H. H. Crapo and G.-C. Rota, On the Foundations of Combinatorial Theory: Combinatorial Geometries, MIT press Cambridge, Mass. (1970).
[4] D. Abdolazimi, A. R. Karlin, N. Klein, S. O. Gharan, Matroid partition property and the secretary problem, arXiv preprint arXiv:2111.12436 (2021).
[5] M. Leichter, B. Moseley, K. Pruhs, On the Impossibility of Decomposing Binary Matroids, arXiv preprint arXiv:2206.12896 (2022).
[6] J. van der Pol, Random GF(q)-representable matroids are not (b,c)-decomposable, arXiv preprint arXiv:2208.05464 (2022).

Leave a Reply