betaFeedback

WorksMathematics

Circuit spectra for binary matroids

Abstract

The circuit spectrum of a matroid is defined to be the set of circuit sizes. The circuit ee-spectrum of a matroid is the set of circuit sizes of the matroid containing the element ee. The circuit spectrum problem is an important problem. Erdős (1992) conjectured that every connected graph GG with girth gg and average degree dd has a cycle spectrum of size at least Ω(d⌊(g−1)/2⌋)Ω(d^{\lfloor (g-1)/2 \rfloor}). Sudakov and Verstraëte (2008) proved the full conjecture of Erdős in a stronger form. It is natural to consider the size of the circuit spectra of binary matroids. Murty (1971) characterized all connected binary matroids with circuit spectra of size one. Lemos et al. (2011) characterized the connected binary matroids with circuit spectra of size two, where the largest size is odd. For general binary matroids, it is still an open question to find a lower bound for the size of the circuit spectra. In this paper, we give best-possible such lower bounds for connected binary matroids that do not contain both the Fano matroid and its dual as minors. Let MM be a simple connected binary matroid that does not have both the Fano matroid and its dual as a minor, and d≥3d\geq 3 be the minimum cocircuit size of MM. We prove that (1) for each element ee of MM, the circuit ee-spectrum of MM must have size at least d−2d-2. This bound is best possible. (2) The circuit spectrum of MM must have size at least d−1d-1, unless M≅F7,F7∗,R10M\cong F_7,F_7^*,R_{10}. In exceptional cases, the spectrum of MM has size equal to d−2d-2.

Paper details

vlnc:W_8aauj2eb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude

View statement
Looking for related papers…