Circuit spectra for binary matroids

The circuit spectrum of a matroid is defined to be the set of circuit sizes. The circuit $e$-spectrum of a matroid is the set of circuit sizes of the matroid containing the element $e$. The circuit spectrum problem is an important problem. Erdős (1992) conjectured that every connected graph $G$ with girth $g$ and average degree $d$ has a cycle spectrum of size at least $Ω(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 $M$ be a simple connected binary matroid that does not have both the Fano matroid and its dual as a minor, and $d\geq 3$ be the minimum cocircuit size of $M$. We prove that (1) for each element $e$ of $M$, the circuit $e$-spectrum of $M$ must have size at least $d-2$. This bound is best possible. (2) The circuit spectrum of $M$ must have size at least $d-1$, unless $M\cong F_7,F_7^*,R_{10}$. In exceptional cases, the spectrum of $M$ has size equal to $d-2$.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-18
DOI
https://doi.org/10.48550/arxiv.2611.23730
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Circuit spectra for binary matroids

Haidong Wu, Shunzhe Zhang, Bing Wei
arXiv (Cornell University)
Advanced Graph Theory Research
preprint

Circuit spectra for binary matroids

Haidong Wu, Shunzhe Zhang, Bing Wei
preprint en

Abstract

The circuit spectrum of a matroid is defined to be the set of circuit sizes. The circuit $e$-spectrum of a matroid is the set of circuit sizes of the matroid containing the element $e$. The circuit spectrum problem is an important problem. Erdős (1992) conjectured that every connected graph $G$ with girth $g$ and average degree $d$ has a cycle spectrum of size at least $Ω(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 $M$ be a simple connected binary matroid that does not have both the Fano matroid and its dual as a minor, and $d\geq 3$ be the minimum cocircuit size of $M$. We prove that (1) for each element $e$ of $M$, the circuit $e$-spectrum of $M$ must have size at least $d-2$. This bound is best possible. (2) The circuit spectrum of $M$ must have size at least $d-1$, unless $M\cong F_7,F_7^*,R_{10}$. In exceptional cases, the spectrum of $M$ has size equal to $d-2$.

arXiv (Cornell University)
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon