Cyclic Orderings and Cyclic Arboricity of Matroids

Details Cyclic Orderings and Cyclic Arboricity of Matroids Cyclic Orderings and Cyclic Arboricity of Matroids

2009-12-15

arxiv.org/abs/0912.2929v3

Mathematics

Combinatorics

12 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Cyclic Orderings and Cyclic Arboricity of Matroids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Cyclic Orderings and Cyclic Arboricity of Matroids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cyclic Orderings and Cyclic Arboricity of Matroids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-306047