MathDB

Kajitani–Ueno–Miyano cyclic orderability conjecture

At least 1 year old · documented by

Let M=(S,B)M=(S,\mathcal{B}) be a matroid with rank function rMr_M. It is uniformly dense if

∣S∣ rM(X)≥rM(S) ∣X∣|S|\,r_M(X)\geq r_M(S)\,|X|

for every X⊆SX\subseteq S. A matroid is cyclically orderable if its ground set has a cyclic ordering in which every interval of rM(S)r_M(S) consecutive elements is a basis. Kajitani–Ueno–Miyano conjecture. A matroid is cyclically orderable if and only if it is uniformly dense. The conjecture is known when ∣S∣|S| and rM(S)r_M(S) are coprime, for sparse paving matroids, and, according to the source, for paving matroids; it remains open in general.

References

Primary source

Kristóf Bérczi, Áron Jánosik and Bence Mátravölgyi, “Cyclic ordering of split matroids”, arXiv:2411.01061 (2024).

cyclic-orderingsmatroid-densitymatroid-theory
Posted · edited
  • Austen F

    The current summary claims:

    "The conjecture is established for several classes, including"... "and rank-at-most-5 matroids"

    Afaik, this is incorrect. I cannot find any of the cited sources establishing KUM for all matroids of rank ≤5. Perhaps the AI is confusing it with Gabow’s cyclic basis-pair conjecture. At the time of writing this comment (Sep 12 2026), the highest rank for which KUM has been established in full is rank-3 via my work: https://doi.org/10.5281/zenodo.21813715

Progress summary

Refreshed
Claimed progress

The conjecture is proved for several important classes of matroids, but no verified proof is known in full generality.

Kajitani, Ueno, and Miyano conjectured that uniform density is exactly equivalent to the existence of a cyclic ordering whose every interval of rank-length is a basis. The general conjecture remains open.

Known results

  • Coprime ∣S∣|S| and rM(S)r_M(S): van den Heuvel and Thomassé, 2011.
  • Sparse paving matroids: Bonin, 2010.
  • Graphic, split, regular, and rank-at-most-55 matroids are among the further established classes.
  • The general conjecture is explicitly described as open in the 2024 split-matroid paper.

2023 paving-matroid result

McGuinness's 2023 paper claims a proof for every paving matroid satisfying uniform density, substantially extending the known cases. The 2024 split-matroid paper records this as progress but does not claim a solution for arbitrary matroids.

Current status (as of September 2026): The conjecture is established for several classes, including coprime size and rank, sparse paving, paving, split, graphic, regular, and rank-at-most-55 matroids, but remains open for general matroids.

Sources

Solutions 0

No solutions have been posted yet.