Paperlane

no. 7 · Tuesday 3 November 2026

A rank bound for bases and circuits in binary matroids

Houshan Fu

math.CO · v3 · 23 pp

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. Using a weighted count of fundamental circuits, we prove that every nonempty simple binary matroid \(M\) 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 settles a conjecture recorded by Oxley in 1983. For every \(e\in E(M)\), we also establish the deletion bound \(b(M\backslash e)\ge d(M)\) and characterize its equality cases. The deletion bound yields a sharp linear lower bound for basis growth under successive series extensions. Finally, under a circuit-size exclusion condition, every pair \((C,e)\) with \(C\) a circuit of a prescribed size and \(e\in C\) can be assigned a distinct basis containing \(C-e\).

comments
23 pages
fields
Combinatorics
pdf ↗ page arXiv:2610.11829 ↗