MathDBKajitani–Ueno–Miyano cyclic orderability conjecture
Kajitani–Ueno–Miyano cyclic orderability conjecture
Let be a matroid with rank function . It is uniformly dense if
for every . A matroid is cyclically orderable if its ground set has a cyclic ordering in which every interval of 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 and are coprime, for sparse paving matroids, and, according to the source, for paving matroids; it remains open in general.
Sources & referencesView supporting material
Primary source
Kristóf Bérczi, Áron Jánosik and Bence Mátravölgyi, “Cyclic ordering of split matroids”, arXiv:2411.01061 (2024).
Progress summary
The conjecture remains open in general, but it has been proved for several important families of matroids.
The Kajitani–Ueno–Miyano conjecture asserts that a matroid admits a cyclic ordering with every rank-sized interval a basis exactly when it satisfies the uniform-density inequalities. The question is associated with Kajitani, Ueno, Miyano, and Wiedemann.
Known results
- Coprime ground-set size and rank: van den Heuvel and Thomassé, 2009.
- Sparse paving matroids: Bonin, 2013.
- Paving matroids: McGuinness, 2023.
- Further recorded classes include graphic, split, regular, and rank at most matroids.
2023–2024 class extensions
McGuinness’s 2023 preprint claims verification for all paving matroids. A 2024 paper on split matroids records additional solved classes and explicitly says the general conjecture remains open; its example obstructs one proposed proof strategy, not the conjecture itself.
Current status (as of August 2026): The conjecture is established for several substantial classes, including coprime size and rank, sparse paving, paving, split, regular, graphic, and rank at most matroids, but remains open for arbitrary matroids.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.