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

o m e g a : E (M) i g h t a r r o w m a t h b b N

, and positive integer

D

, the following are equivalent. (1) For all

A s u b s e t e q E (M)

, we have

s u m_{a i n A} o m e g a (a) l e D c d o t r (A)

. (2) There is a map

p h i

that assigns to each element

e

of

E (M)

a set

p h i (e)

of

o m e g a (e)

cyclically consecutive elements in the cycle

(1, 2, ..., D)

so that each set

e | i i n p h i (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 s u b s e t e q E (M)

, we have

| A | / r (A) l e | 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.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Cyclic orderings and cyclic arboricity of matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414636)