On the Cogirth of Binary Matroids

DOI10.1016/J.AAM.2023.102515MaRDI QIDQ6369184arXivFDO

Authors Cameron Crenshaw, James Oxley

Publication date 1 June 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.AAM.2023.102515

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Combinatorial aspects of matroids and geometric lattices (05B35) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

arXiv classification

math.CO

Abstract: The cogirth, $g^{a}st(M)$, of a matroid $M$ is the size of a smallest cocircuit of $M$. Finding the cogirth of a graphic matroid can be done in polynomial time, but Vardy showed in 1997 that it is NP-hard to find the cogirth of a binary matroid. In this paper, we show that $g^{a}st(M)leqfrac12vertE(M)vert$ when $M$ is binary, unless $M$ simplifies to a projective geometry. We also show that, when equality holds, $M$ simplifies to a Bose-Burton geometry, that is, a matroid of the form $PG(r-1,2)-PG(k-1,2)$. These results extend to matroids representable over arbitrary finite fields.

This page was built for publication: On the Cogirth of Binary Matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6369184)