On Density-Critical Matroids

Abstract

For a matroid $M$ having $m$ rank-one flats, the density $d(M)$ is $\frac{m}{r(M)}$ unless $m=0$, in which case $d(M)=0$. A matroid is density-critical if all of its proper minors of non-zero rank have lower density. By a 1965 theorem of Edmonds, a matroid that is minor-minimal among simple matroids that cannot be covered by $k$ independent sets is density-critical. It is straightforward to show that $U_{1,k+1}$ is the only minor-minimal loopless matroid with no covering by $k$ independent sets. We prove that there are exactly ten minor-minimal simple obstructions to a matroid being able to be covered by two independent sets. These ten matroids are precisely the density-critical matroids $M$ such that $d(M)>2$ but $d(N)\le 2$ for all proper minors $N$ of $M$. All density-critical matroids of density less than $2$ are series-parallel networks. For $k\ge 2$, although finding all density-critical matroids of density at most $k$ does not seem straightforward, we do solve this problem for $k=\frac{9}{4}$.

16 pages