Kajitani–Miyano–Ueno conjecture on cyclically orderable matroids

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 XE(M)X\subseteq E(M), define

β(X)=Xr(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"001FXE(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 XE(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.

Sources & referencesView supporting material

Primary source

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

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.