# 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 , 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  on the covering number of the intersection of two matroids, Bérczi, Schwarcz, and Yamaguchi  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  and Leichter, Moseley, and Pruhs  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  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.

References
 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).
 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).
 H. H. Crapo and G.-C. Rota, On the Foundations of Combinatorial Theory: Combinatorial Geometries, MIT press Cambridge, Mass. (1970).
 D. Abdolazimi, A. R. Karlin, N. Klein, S. O. Gharan, Matroid partition property and the secretary problem, arXiv preprint arXiv:2111.12436 (2021).
 M. Leichter, B. Moseley, K. Pruhs, On the Impossibility of Decomposing Binary Matroids, arXiv preprint arXiv:2206.12896 (2022).
 J. van der Pol, Random GF(q)-representable matroids are not (b,c)-decomposable, arXiv preprint arXiv:2208.05464 (2022).