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].
Bonin [5] proved the conjecture for sparse paving matroids, and later McGuiness [6] verified it for all 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, 2009, DOI link, arXiv link.
- ↑ J.E. Bonin, Basis-exchange properties of sparse paving matroids, 2010, Author link, arXiv link.
- ↑ S. McGuiness, Cyclic Orderings of Paving Matroids, 2023, arXiv link.
