# Cyclic orderings of matroids

Let *M* be a matroid on ground set *S*, and suppose that *S* can be partitioned into k bases. Is it true that there is a cyclic ordering of the elements of *S* such that any [math]|S|/k[/math] consecutive elements in this ordering form a basis?

## Remarks

The conjecture was suggested by Kajitani, Ueno and Miyano ^{[1]}, and a similar question was asked earlier by Gabow ^{[2]}. The case *k=2* and *M* graphic follows from the constructive characterization of graphs decomposable into two spanning trees. For *k=2*, the conjecture is open for linear matroids, and for *k≥3*, it is open even for graphic matroids. Gu, Horacek, and Lai ^{[3]} prove the conjecture for some graph classes, including complete bipartite graphs. Note that the conjecture on the Equitability of matroids is a weaker version of the present conjecture for *k=2*.

A related result by van den Heuvel and Thomassé ^{[4]} is that the circular covering number of a loopless matroid equals its fractional covering number. They also proved the following theorem:

**Theorem ^{[4]}.** Let

*M*be a matroid on ground set

*S*with rank function

*r*, such that [math]\mbox{gcd}(|S|,r(S))=1[/math]. There is a cyclic ordering of the elements of

*S*such that any

*r(S)*consecutive elements in this ordering form a basis if and only if [math]r(S)|X| \leq |S|r(X)[/math] for every [math]X \subseteq S[/math].

Recently Bonin ^{[5]} proved the conjecture for sparse paving matroids.

## References

- ↑ Y. Kajitani, S. Ueno, H. Miyano,
*Ordering of the elements of a matroid such that its consecutive w elements are independent*, Discrete Mathematics 72 (1988), 187-194. DOI link. - ↑ H. Gabow,
*Decomposing symmetric exchanges in matroid bases*, Mathematical Programming 10 (1976), 271-276. DOI link. - ↑ X. Gu, K. Horacek, H.J. Lai,
*Cyclic base orderings in some classes of graphs*, author link - ↑
^{4.0}^{4.1}J. van den Heuvel, S. Thomassé,*Cyclic Orderings and Cyclic Arboricity of Matroids*, DOI link, arXiv link. - ↑ J.E. Bonin,
*Basis-exchange properties of sparse paving matroids*, Author link, arXiv link.