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ω:E(M)→N, and positive integer D, the following are equivalent. (1) For allA⊆E(M), we have∑a∈Aω(a)⩽D⋅r(A). (2) There is a map ϕ that assigns to each element e ofE(M)a setϕ(e)ofω(e)cyclically consecutive elements in the cycle(1,2,...,D)so that each set{e|i∈ϕ(e)}, fori=1,...,D, is independent. As a first corollary we obtain the following. For each matroid M such that|E(M)|andr(M)are coprime, the following are equivalent. (1) For all non-emptyA⊆E(M), we have|A|/r(A)⩽|E(M)|/r(M). (2) There is a cyclic permutation ofE(M)in which all sets ofr(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.
Type de document :
Article dans une revue
Journal of Combinatorial Theory, Series B, Elsevier, 2012, 102, pp.638-646. 〈10.1016/j.jctb.2011.08.004〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00806762
Contributeur : Alexandre Pinlou <>
Soumis le : mardi 2 avril 2013 - 12:02:25
Dernière modification le : mardi 24 avril 2018 - 13:52:09

Lien texte intégral

Identifiants

Citation

Jan Van den Heuvel, Stéphan Thomassé. Cyclic orderings and cyclic arboricity of matroids. Journal of Combinatorial Theory, Series B, Elsevier, 2012, 102, pp.638-646. 〈10.1016/j.jctb.2011.08.004〉. 〈lirmm-00806762〉

Partager

Métriques

Consultations de la notice

162