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 disproved high confidence

As written, the conjecture is false: the uniformly colored matroid U_{n-1,2n} has no circuit shorter than n.

Cited literature (2)

counterexample Short rainbow cycles in graphs and matroids (2018)

See linked article · Existing literature or final source version

As written, the conjecture is false: the uniformly colored matroid U_{n-1,2n} has no circuit shorter than n.

Read the literature-status audit
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. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: This does not address variants restricted to binary or regular matroids, since the uniform counterexamples used here are not binary.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

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