Description
The authors show that if the ground set of a matroid can be partitioned into k \geq 2 bases, then for any given subset S of the ground set, there is a partition into k bases such that the sizes of the intersections of the bases with S may differ by at most one. This settles the matroid equitability conjecture by Fekete and Szabó (Electron. J. Comb. 2011) in the affirmative. They also investigate equitable splittings of two disjoint sets S_1 and S_2, and show that there is a partition into bases such that the sizes of the intersections with S_1 may differ by at most one and the sizes of the intersections with S_2 may differ by at most two; this is the best possible one can hope for arbitrary matroids.
The authors also derive applications of this result into matroid constrained fair division problems. They show that there exists a matroid-constrained fair division that is envy-free up to 1 item if the valuations are identical and tri-valued additive. They also show that for bi-valued additive valuations, there exists a matroidconstrained allocation that provides everyone their maximin share.
Main article: Hannaneh Akrami, Roshan Raj, László A. Végh: Matroids are Equitable https://arxiv.org/abs/2507.12100