Resource title

Cyclic orderings and cyclic arboricity of matroids

Resource image

image for OpenScout resource :: Cyclic orderings and cyclic arboricity of matroids

Resource description

We prove a general result concerning cyclic orderings of the elements of a matroid. For each matroid $M$, weight function $\omega:E(M)\rightarrow\mathbb{N}$, and positive integer $D$, the following are equivalent. (1) For all $A\subseteq E(M)$, we have $\sum_{a\in A}\omega(a)\le D\cdot r(A)$. (2) There is a map $\phi$ that assigns to each element $e$ of $E(M)$ a set $\phi(e)$ of $\omega(e)$ cyclically consecutive elements in the cycle $(1,2,...,D)$ so that each set $\{e|i\in\phi(e)\}$, for $i=1,...,D$, is independent. As a first corollary we obtain the following. For each matroid $M$ so that $|E(M)|$ and $r(M)$ are coprime, the following are equivalent. (1) For all non-empty $A\subseteq E(M)$, we have $|A|/r(A)\le|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.

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

Resource resource URL

http://eprints.lse.ac.uk/27681/

Resource license