Equitability of matroids

From Egres Open
Jump to: navigation, search

Is it true that if the ground set S of a matroid M can be partitioned into 2 bases, then for any set [math]X \subseteq S[/math] there is a basis B such that [math]S \setminus B[/math] is also a basis and [math]\lfloor|X|/2 \rfloor \leq |B\cap X| \leq \lceil|X|/2 \rceil[/math]?


Remarks

The matroids with the above property are called equitable. The conjecture would be a consequence of the conjecture on Cyclic orderings of matroids: if there is a cyclic ordering such that any [math]|S|/2[/math] consecutive elements form a basis, then it is easy to see that for any [math]X \subseteq S[/math] one of these cyclically consecutive bases has the above property.

It was shown by Fekete and Szabó [1] that graphic matroids and weakly base orderable matroids are equitable, and they also investigated related problems where equitability with respect to more than one set is required. Szabó also showed that every matroid on at most 8 elements is equitable.

References

  1. Z. Fekete, J. Szabó, Equitable partitions into spanning trees in a graph, journal link. See also EGRES Technical Report No. 2005-03.