Circuit decompositions of binary matroids

Abstract

Given a simple Eulerian binary matroid $M$, what is the minimum number of disjoint circuits necessary to decompose $M$? We prove that $|M|/(\mathrm{rank}(M)+1)$ many circuits suffice if $M={\mathbb{F}}_2^n\setminus \{0\}$ is the complete binary matroid, for certain values of $n$, and that $\mathcal{O}(2^{\mathrm{rank}(M)}/(\mathrm{rank}(M)+1))$ many circuits suffice for general $M$. We also determine the asymptotic behaviour of the minimum number of circuits in an odd-cover of $M$.

10 pages