Short rainbow circuits in rank-(n-1) matroids

Conjecture 12 · arXiv:1806.00825

arXiv Conjecture medium confidence— first stated 2020-05-07

Authors: Matt DeVos, Matthew Drescher, Daryl Funk, Sebastián González Hermosillo de la Maza, Krystal Guo, Tony Huynh, Bojan Mohar, Amanda Montejano

Status partial high confidence

The conjecture holds for graphic matroids (by Theorem 5 of the source paper) and cographic matroids (Theorem 13 of the source paper). A 2026 paper by McGuinness (arXiv:2601.17624) extends the result to all regular matroids, proving that every simple regular matroid of rank r with r+1 colour classes of size at least 2 contains a rainbow circuit of size at most ⌈(r+1)/2⌉. The full conjecture for arbitrary simple rank-(n-1) matroids fails: the source paper itself notes that uniform matroids U_{n-1,m} (for large m) provide counterexamples, as their circuits all have size n.

Cited literature (1)

partial Short Rainbow Circuits in Regular Matroids (2026)

Sean McGuinness · arXiv preprint · arXiv:2601.17624

Proves the conjecture for the class of regular matroids, showing that every simple regular matroid M with r(M)+1 colour classes of size at least 2 contains a rainbow circuit of size at most ⌈(r(M)+1)/2⌉.

Reviewer notes. The conjecture as literally stated (for all simple rank-(n-1) matroids) is known to be false via uniform-matroid counterexamples noted in the source paper. The meaningful open question is whether the result extends beyond regular matroids to broader classes. The internal corpus references (both copies of arXiv:2101.04716) are false positives matching a different conjecture in a different paper.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. Let $M$ be a simple rank-$(n-1)$ matroid and $c$ be a colouring of $E(M)$ with $n$ colours, where each colour class has size at least $2$. Then $M$ contains a rainbow circuit of size at most $\lceil n/2 \rceil$.

Context

Proposed as the natural matroid analogue of Theorem 5. The authors note it holds for graphic matroids (by Theorem 5) and prove it for cographic matroids (Theorem 13), but observe it fails for general binary matroids because the uniform matroid $U_{n-1,m}$ contains no circuits of size less than $n$.

Notes. PDF source — ceiling notation garbled but mathematical content is unambiguous.

Source paper

Short rainbow cycles in graphs and matroids
Matt DeVos, Matthew Drescher, Daryl Funk, Sebastián González Hermosillo de la Maza, Krystal Guo, Tony Huynh, Bojan Mohar, Amanda Montejano · 2020-05-07
https://arxiv.org/abs/1806.00825 PDF source