Cyclic basis orderings of uniformly dense rank-three matroids
Follow the latest progress by email.
A finite matroid is uniformly dense if no subset has a larger size-to-rank ratio than the whole ground set. Does every uniformly dense rank-three matroid admit a cyclic ordering in which every consecutive triple is a basis?
Why it matters and what counts as progress
Why it matters: The divisible ground-set case completes the rank-three question beyond the known coprime and paving cases.
What counts as progress: A cyclic basis ordering for every uniformly dense rank-three matroid with |E| divisible by three, including non-simple and non-paving examples, or a counterexample.
How the problem developed
- 1988 · Conjecture [1]
Yoji Kajitani, Shuichi Ueno and Hiroshi Miyano Conjectured that uniform density is sufficient for a matroid to admit a cyclic ordering whose every rank-length interval is a basis.
- 2012 · Partial theorem [2]
J. van den Heuvel and S. Thomassé Proved cyclic orderability when ground-set size and matroid rank are coprime, leaving divisible cases outside that result.
Austen Fletcher Reported a proof for the remaining rank-three case with ground-set size divisible by three and supplied a Lean 4 formalization of that case.
AI contribution
Lean checks the divisible rank-three matroid case
For every finite uniformly dense rank-three matroid M with |E(M)|=3k and k>0, the version-2 Lean theorem constructs a cyclic ordering in which each consecutive triple is a basis. It includes non-simple and non-paving matroids.
Sources
- Kajitani, Ueno and Miyano, Ordering of the elements of a matroid such that its consecutive w elements are independent
- van den Heuvel and Thomassé, Cyclic orderings and cyclic arboricity of matroids
- Fletcher, accompanying rank-three mathematical paper
- Fletcher, Rank3KUM: Lean 4 Formalization of the Divisible Rank-Three Case
- Fletcher, Rank3KUM version-2 theorem and verification
Website timeline
Publication dates and editorial changes.