Cyclic basis orderings of uniformly dense rank-three matroids

Abstract

A matroid M is uniformly dense if no subset is denser than the ground set, and has a cyclic basis ordering if its ground set can be arranged in a cycle so that every r(M) consecutive elements form a basis. Kajitani, Ueno and Miyano conjectured in 1988 that the second property is equivalent to the first; necessity is immediate and sufficiency is open in general. We prove sufficiency for matroids of rank three whose ground set has size divisible by three, with no restriction to representable, paving, simple or graphic matroids. Together with the theorem of van den Heuvel and Thomassé for the coprime case, this shows that every finite uniformly dense matroid of rank three has a cyclic basis ordering. The case not previously available in the literature is that of rank-three matroids possessing a nontrivial parallel class, the simple case having been settled by McGuinness for all paving matroids. The proof is formalized in Lean 4. Version-2 revises and simplifies several parts of the proof presentation, strengthens the near-tight-flat analysis, replaces the six-element finite-certificate exposition with a structural argument, improves the correspondence between the paper and the Lean development, and expands the discussion of the relation to McGuinness’s deletion-and-two-gap insertion argument.The accompanying version-2 Lean 4 formalization is archived separately at:https://doi.org/10.5281/zenodo.21813154