Skip to Main content Skip to Navigation
Conference papers

Cyclic Orderings of Matroids

Stéphan Thomassé 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Answering a question Kajitani \emph{et al} and Wiedemann, we prove that if $B_1,\ldots,B_k$ are bases of a matroid of rank~$r$, then the list of $k\cdot r$ elements of these bases has a cyclic ordering in which every cyclic interval of~$r$ elements is a base. The following particular case of this question was already known: If an $n$-vertex graph $G$ is the (edge) union of two spanning trees, the edges of $G$ can be cyclically enumerated in such a way that every cyclic interval of $n-1$ edges is a tree. We therefore extend this result for more than two trees, and for general bases of matroids. Althought this result would suggest the introduction of some stronger exchange axiom (the existence of a linear, instead of cyclic, ordering indeed follows from the usual exchange axiom), it turns out that the proof is based on a fractional approach. Indeed for matroids, the fractional chromatic number is equal to the circular chromatic number. The proof of this result, conjectured by Gonçalves, turns out to be the key of the existence of cyclic orderings. We will conclude this talk by a discussion on open problems in the area, focusing on two conjectures of Rota and Gabow.
Document type :
Conference papers
Complete list of metadata
Contributor : Stephan Thomasse <>
Submitted on : Friday, September 26, 2008 - 1:52:49 PM
Last modification on : Tuesday, January 22, 2019 - 7:10:05 PM


  • HAL Id : lirmm-00325158, version 1



Stéphan Thomassé. Cyclic Orderings of Matroids. LAGOS: Latin-American Algorithms, Graphs and Optimization Symposium, Nov 2007, Puerto Varas, Chile. ⟨lirmm-00325158⟩



Record views