MathDB

Kajitani–Miyano–Ueno conjecture on cyclically orderable matroids

About 3 years old · traced to

Let MM be a matroid with ground set E(M)E(M) and rank function rr. A matroid is cyclically orderable if it has a cyclic permutation of its elements such that any r(M)r(M) consecutive elements form a basis. For every nonempty subset X⊆E(M)X\subseteq E(M), define

β(X)=∣X∣r(X)\beta(X)=\frac{|X|}{r(X)}

when r(X)≠0r(X)\ne 0, and define β(X)=∞\beta(X)=\infty otherwise. Let

γ(M)=max⁡\mathchar"001F≠X⊆E(M)β(X).\gamma(M)=\max_{\mathchar"001F\ne X\subseteq E(M)}\beta(X).

Kajitani–Miyano–Ueno conjecture. The matroid MM is cyclically orderable if and only if

γ(M)=β(E(M)).\gamma(M)=\beta(E(M)).

Equivalently, this asserts that cyclic orderability is characterized by ∣X∣/r(X)≤∣E(M)∣/r(M)|X|/r(X)\le |E(M)|/r(M) for every nonempty X⊆E(M)X\subseteq E(M), with the stated convention when r(X)=0r(X)=0. The paper verifies the conjecture for all paving matroids, but the general case is not resolved here.

References

Primary source

Sean McGuinness, “Cyclic Orderings of Paving Matroids”, arXiv:2308.12239 (2024).

cyclic-orderingsmatroid-theorypaving-matroids
Posted · edited

Progress summary

Refreshed
Open

The conjecture remains open in general, with proofs only for several important subclasses such as paving matroids.

The Kajitani–Miyano–Ueno conjecture says that the density condition γ(M)=β(E(M))\gamma(M)=\beta(E(M)) exactly characterizes cyclic orderability. No source gives a date for its original formulation; the general assertion remains unresolved.

Known results

  • Van den Heuvel and Thomassé proved the conjecture when gcd⁡(∣E(M)∣,r(M))=1\gcd(|E(M)|,r(M))=1 (2009).
  • Sparse paving matroids satisfy the conjecture; the retrieved sources record this as an earlier result.
  • McGuinness proved the conjecture for all paving matroids (2023).

2024 split-matroid result

A 2024 paper proves cyclic orderability for a special class of split matroids whose ground set decomposes into pairwise disjoint bases. It neither proves nor disproves the general conjecture.

Current status (as of September 2026): The conjecture is proved for several subclasses, including paving matroids and the coprime case, but remains open for arbitrary matroids.

Sources

Solutions 0

No solutions have been posted yet.