Cyclic Orderings of Paving Matroids

  • Sean McGuinness

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.

Published
2024-10-04
Article Number
P4.9