Cyclic orderings of matroids

From Egres Open
Jump to: navigation, search

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

  1. 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.
  2. H. Gabow, Decomposing symmetric exchanges in matroid bases, Mathematical Programming 10 (1976), 271-276. DOI link.
  3. X. Gu, K. Horacek, H.J. Lai, Cyclic base orderings in some classes of graphs, author link
  4. 4.0 4.1 J. van den Heuvel, S. Thomassé, Cyclic Orderings and Cyclic Arboricity of Matroids, DOI link, arXiv link.
  5. J.E. Bonin, Basis-exchange properties of sparse paving matroids, Author link, arXiv link.