Cyclic orderings and cyclic arboricity of matroids

AbstractWe prove a general result concerning cyclic orderings of the elements of a matroid. For each matroid M, weight function ω:E(M)→N, and positive integer D, the following are equivalent. (1) For all A⊆E(M), we have ∑a∈Aω(a)⩽D⋅r(A). (2) There is a map ϕ that assigns to each element e of E(M) a set ϕ(e) of ω(e) cyclically consecutive elements in the cycle (1,2,…,D) so that each set {e|i∈ϕ(e)}, for i=1,…,D, is independent.As a first corollary we obtain the following. For each matroid M such that |E(M)| and r(M) are coprime, the following are equivalent. (1) For all non-empty A⊆E(M), we have |A|/r(A)⩽|E(M)|/r(M). (2) There is a cyclic permutation of E(M) in which all sets of r(M) 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