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.
Type de document :
Communication dans un congrès
LAGOS: Latin-American Algorithms, Graphs and Optimization Symposium, Nov 2007, Puerto Varas, Chile. IV Latin-American Algorithms, Graphs and Optimization Symposium, 2007, 〈http://www.dii.uchile.cl/~lagos07/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00325158
Contributeur : Stephan Thomasse <>
Soumis le : vendredi 26 septembre 2008 - 13:52:49
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

  • HAL Id : lirmm-00325158, version 1

Collections

Citation

Stéphan Thomassé. Cyclic Orderings of Matroids. LAGOS: Latin-American Algorithms, Graphs and Optimization Symposium, Nov 2007, Puerto Varas, Chile. IV Latin-American Algorithms, Graphs and Optimization Symposium, 2007, 〈http://www.dii.uchile.cl/~lagos07/〉. 〈lirmm-00325158〉

Partager

Métriques

Consultations de la notice

40