A rank bound for bases and circuits in binary matroids

Source abstract

Let $b(M)$, $d(M)$, and $r(M)$ denote the number of bases, the number of circuits, and the rank of a matroid $M$, respectively. We prove that every nonempty simple binary matroid with no coloops satisfies $$2b(M)\ge(r(M)+1)d(M),$$ with equality if and only if $M$ is isomorphic to the Fano matroid. This confirms a conjecture recorded by Oxley in 1983. For the same class, we prove that deleting any element leaves at least as many bases as there are circuits in the original matroid: $b(M\backslash e)\ge d(M)$ for every $e\in E(M)$. We determine all equality cases and deduce a sharp linear lower bound for basis growth under successive series extensions. The main counting step is a joint estimate for the three largest possible circuit sizes, obtained from contraction-normalized fundamental-circuit counts and an exact folded-cube edge correspondence.