Joins and ear decompositions beyond graphic matroids

Abstract

For a matroid $M$, a join is a set $J\subseteq E(M)$ that meets every circuit $C$ in at most $|C|/2$ elements. Let $\mu(M)$ denote the maximum size of a join. Motivated by Frank's min--max theorem for graphic matroids, we compare $\mu(M)$ with an ear-decomposition parameter $\eta(M)=(r(M)+\varphi(M))/2$, where $\varphi(M)$ is the minimum number of even lobes in an ear decomposition of $M$. Frank's theorem implies $\mu(M)=\eta(M)$ for connected graphic matroids. Here we study how far this equality extends beyond graphic matroids. We show that the exact equality does not hold in general: it already fails for cographic matroids, hence within the binary class. Furthermore, the class of matroids satisfying $\mu(M)=\eta(M)$ is not minor-closed, thus there is little hope for a forbidden minor characterization. We also prove that computing a maximum join is NP-hard for cographic matroids, hard to approximate within a factor of $519/520$, and NP-hard for sparse paving matroids given by their list of bases. Despite these negative results, we show that the two parameters remain quantitatively comparable in several natural classes. We prove comparison bounds for binary, paving, cographic, and arbitrary connected matroids. In particular, using Seymour's decomposition theorem, we combine the equality for graphic matroids, the bound for cographic matroids, and a direct analysis of $R_{10}$ to obtain $\eta(M)\leq 6\mu(M)-2$ for every regular matroid $M$.