Cyclic orderings of paving matroids

Sean McGuinness¹

¹Thompson Rivers University

The electronic journal of combinatorics, Tome 31 (2024) no. 4

Résumé

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.

Détail

DOI : 10.37236/12328

Classification : 05B35
Mots-clés : orderings on a matroid, \(w\)th C-ind ordering