Cyclic Orderings of Matroids - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2007

Cyclic Orderings of Matroids

Stéphan Thomassé

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.
No file

Dates and versions

lirmm-00325158 , version 1 (26-09-2008)

Identifiers

  • HAL Id : lirmm-00325158 , version 1

Cite

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

Share

Gmail Facebook X LinkedIn More