Cyclic Orderings of Paving Matroids

A matroid M of rank r is cyclically orderable if there is a cyclic permutation of the elements of M such that any r consecutive elements form a basis in M. An old conjecture of Kajitani, Miyano, and Ueno states that a matroid M is cyclically orderable if and only if for all ∅ ≠ X ⊆ E(M), |X|/r(X) ≤ |E(M)|/r(M). In this paper, we verify this conjecture for all paving matroids.