Cyclic Orderings of Paving Matroids
Abstract
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 $\emptyset \ne X \subseteq E(M), \frac {|X|}{r(X)} \le \frac {|E(M)|}{r(M)}.$ In this paper, we verify this conjecture for all paving matroids.