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.

Aharoni et al. [2] conjecture that the ground set S can be partitioned into 2 independent sets in two matroids [math]M_1,M_2[/math], then for any set [math]X \subseteq S[/math] there is a common independent set [math]I[/math] such that [math]|I\cap X| \geq |X|/2-1[/math] and [math]|I\setminus X| \geq |S \setminus X|/2-1[/math]. They proved the weaker inequalities [math]|I\cap X| \geq (\frac{1}{2}-\frac{1}{|V|})|X|-1[/math] and [math]|I\setminus X| \geq (\frac{1}{2}-\frac{1}{|V|})|S \setminus X|-1[/math].

References

  1. Z. Fekete, J. Szabó, Equitable partitions to spanning trees in a graph, DOI link. See also EGRES Technical Report No. 2005-03.
  2. R. Aharoni, E. Berger, D. Kotlar, R. Ziv, Fair Representation in the Intersection of Two Matroids, The Electronic Journal of Combinatorics 2017, DOI link.