Cyclic Orderings of Matroids - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

Cyclic Orderings of Matroids

Stéphan Thomassé

Résumé

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.
Fichier non déposé

Dates et versions

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

Identifiants

  • HAL Id : lirmm-00325158 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More