Large circuits in binary matroids of large cogirth. I (Q1127871)

The purpose of this paper is to extend two classical results concerning the existence of long circuits in a simple 2-connected graph \(G\) to a simple connected regular matroid \(M\), or more generally to a simple connected binary matroid \(M\) with certain forbidden minors, including the class of regular matroids. The first result, due to G. A. Dirac, states that if \(G\) has minimum degree \(d\geq| V(G)|/2\), then \(G\) is hamiltonian. The second result, due to P. Erdős and T. Gallai, states that if \(e= uv\in E(G)\) and every vertex of \(V(G)- \{u,v\}\) has degree at least \(d\), then \(G\) has a circuit \(C\) containing \(e\) and of size at least \(d+1\). Our extension of Dirac's theorem is to show that if every cocircuit of \(M\) has size at least \(d\geq (r(M)+1)/2\) then \(M\) has a circuit of size \(r(M)+1\). Our extension of the Erdős-Gallai theorem is to show that, if \(e\in E(M)\) and every cocircuit of \(M\) disjoint from \(e\) has size at least \(d\geq 3\), then \(M\) has a circuit of size at least \(d+1\) containing \(e\). The extension of Dirac's theorem was conjectured by D. J. A. Welsh. The extension of the Erdős-Gallai result generalises a result of R. E. Bixby and W. H. Cunningham that if \(M\) is a simple binary matroid with no \(F_7\)-minor and every cocircuit of \(M\) has size at least \(d\), then \(r(M)\geq d\).