Cyclic orderings and cyclic arboricity of matroids

Abstract: We prove a general result concerning cyclic orderings of the elements of a matroid. For each matroid M, weight function , and positive integer D, the following are equivalent. (1) For all , we have . (2) There is a map ϕ that assigns to each element e of a set of cyclically consecutive elements in the cycle so that each set , for , is independent. As a first corollary we obtain the following. For each matroid M such that and are coprime, the following are equivalent. (1) For all non-empty , we have . (2) There is a cyclic permutation of in which all sets of cyclically consecutive elements are bases of M. A second corollary is that the circular arboricity of a matroid is equal to its fractional arboricity. These results generalise classical results of Edmonds, Nash-Williams and Tutte on covering and packing matroids by bases and graphs by spanning trees. [Copyright &y& Elsevier]