Cyclic Orderings of Matroids
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.