TOPICS
Search

Kajitani-Ueno-Miyano Conjecture


The Kajitani-Ueno-Miyano conjecture (Kajitani et al. 1988) states that a finite matroid admits a cyclic basis ordering iff it is a uniformly dense matroid.

Van den Heuvel and Thomassé (2012) proved the conjecture when the cardinality |E| of the ground set and the matroid rank r(M) are relatively prime. Fletcher (2026a) reported a proof of the remaining case of matroid rank 3, in which |E| is divisible by 3. His theorem states that for every positive integer k, every finite uniformly dense matroid of matroid rank 3 on 3k elements admits a cyclic basis ordering. Together, the two results give the claimed conclusion for all finite matroids of matroid rank 3.

Fletcher (2026a) credits GPT-5.6 Sol with developing the central argument under his direction. GPT-5.6 Sol and Claude Opus 5 produced the original Lean 4 formalization and manuscript, while GPT-6 Astra and Fable 5.1 assisted the review and refinement of version 2. The theorem for |E| divisible by 3 is formalized end-to-end in Lean 4 (Fletcher 2026b). The published theorem for the relatively prime case used to obtain the full conclusion is not formalized there. As of Sep. 11, 2026, no independent specialist verification or peer review of the new argument had been reported (VibeMathed 2026). The general conjecture remains open for higher matroid ranks.


See also

Cyclic Basis Ordering, Ground Set, Matroid, Matroid Basis, Matroid Rank, Uniformly Dense Matroid

Explore with Wolfram|Alpha

References

Fletcher, A. "Cyclic Basis Orderings of Uniformly Dense Rank-Three Matroids." Version 2, Sep. 10, 2026a. https://doi.org/10.5281/zenodo.22698709.Fletcher, A. "Rank3KUM: A Lean 4 Formalization of the Divisible Case of the Rank-Three Kajitani-Ueno-Miyano Cyclic Basis Ordering Theorem." Version 2.0.0, Sep. 11, 2026b. https://doi.org/10.5281/zenodo.22698862.Kajitani, Y.; Ueno, S.; and Miyano, H. "Ordering of the Elements of a Matroid Such That Its Consecutive w Elements Are Independent." Disc. Math. 72, 187-194, 1988. https://doi.org/10.1016/0012-365x(88)90209-9.van den Heuvel, J. and Thomassé, S. "Cyclic Orderings and Cyclic Arboricity of Matroids." J. Combin. Th. Ser. B 102, 638-646, 2012. https://doi.org/10.1016/j.jctb.2011.08.004.VibeMathed. "The Divisible Rank-Three Case of the Kajitani-Ueno-Miyano Conjecture." Sep. 10, 2026. https://vibemathed.com/problem/divisible-rank-three-case-of-the-kajitani-ueno-miyano-conjecture.

Cite this as:

Weisstein, Eric W. "Kajitani-Ueno-Miyano Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Kajitani-Ueno-MiyanoConjecture.html

Subject classifications